数据库为什么应用 B + 树？
前言
讲到索引，第一反馈必定是能进步查问效率。例如书的目录，想要查找某一章节，会先从目录中定位。如果没有目录，那么就须要将所有内容都看一遍能力找到。
索引的设计对程序的性能至关重要，若索引太少，对查问性能受影响；而如果索引太多，则会影响增 / 改 / 删等的性能。
知识点
MySQL 中个别反对以下几种常见的索引：
B+ 树索引
全文索引
哈希索引
咱们明天重点来讲下 B + 树索引，以及为什么要用 B + 树来作为索引的数据结构。
B+ 树索引并不能间接找到具体的行，只是找到被查找行所在的页，而后 DB 通过把整页读入内存，再在内存中查找。
1. 与二叉树相比
二叉树相比于程序查找确实缩小了查找次数，然而在最坏状况下，二叉树有可能进化为程序查找。而且就二叉树自身来说，当数据库的数据量特地大时，其层数也将特地大。二叉树的高度个别是 log_2^n，B 树的高度是 log_t^((n+1)/2) + 1，其高度约比 B 树大 lgt 倍。n 是节点总数，t 是树的最小度数。
2. 与 B 树相比
B 树在进步 IO 性能的同时，并没与解决元素遍历时效率低下的问题，正是为了解决这个问题，B+ 数应运而生。B+ 数只需遍历叶子节点即可实现整棵树的遍历，而 B 树必须应用中序遍历按序扫库，B+ 树反对范畴查问十分不便。这才是数据库选用 B + 树的次要起因。
另外，最初说一下，并不是说 B + 树就比 B 树好，有很多基于频率的搜寻是选用 B 树，越频繁 query 的结点越往根上走，前提是须要对 query 做统计，而且要对 key 做一些变动。
无论是 B 树还是 B + 树因为前边几层重复 query，因而早已被加载入内存，不会呈现读磁盘 IO。个别启动的时候，就会被动换入内存。在内存中 B + 树并没有劣势，只有在磁盘中 B + 树的威力能力浮现。
采纳 B + 树的索引构造长处：
B+ 树的高度个别为 2 - 4 层，所以查找记录时最多只须要 2 - 4 次 IO，绝对二叉均衡树曾经大大降低了。范畴查找时，能通过叶子节点的指针获取数据。例如查找大于等于 3 的数据，当在叶子节点中查到 3 时，通过 3 的尾指针便能获取所有数据，而不须要再像二叉树一样再获取到 3 的父节点。总结：
1)二叉查找树 (BST): 解决了排序的根本问题, 然而因为无奈保障均衡, 可能进化为链表
2) 均衡二叉树 (AVⅥL): 通过旋转解决了均衡的问题, 然而旋转操作效率太低
3) 红黑树: 通过舍弃严格的均衡和引入红黑节点, 解决了 AⅥ旋转效率过低的问题, 然而在磁盘等场景下, 树依然太高,IO 次数太多
4)B 树: 通过将二叉树改为多路均衡查找树, 解决了树过高的问题
5)B+ 树: 在 B 树的根底上, 将非叶节点革新为不存储数据的纯索引节点, 进一步升高了树的高度; 此外将叶节点应用指针连接成链表, 范畴查问更加高效。
仅做学习应用，权侵删，禁止转发
参考：
https://blog.csdn.net/qq_3803…
https://www.cnblogs.com/tongo…
https://www.bilibili.com/read…
http://www.coder55.com/questi…