文章目录 一、非B+树不可吗？二、二叉树演变B+树过程三、B+树总结四、和B树的关系 一、非B+树不可吗？
数据库最常用的两个功能就是“等值查询”和“范围查询”。如果只是为了满足“等值查询”，那么Hash散列表和平衡二叉查找树都能胜任数据库索引这个使用场景，但是“范围查询”却加大了难度，使得它们不太适合了。
在原先讲过的“跳表”倒是很契合，但实际场景中，大家都是使用的B+树。
二、二叉树演变B+树过程二叉树我们前面也都了解过了，我们来看下，用它来作为索引的数据结构会存在什么问题？首先它是能够满足“等值查询”的，但是无法进行“范围查询”，所以，我们需要对其进行改造：
树中的每个节点都不存储具体的数据，而是存储索引；叶子节点从左到右用双向链表绑定起来；改造前后的二叉树结构示意图如下：
改造后的好处是：
只是存储索引的话，使得二叉树的大小不会很大；叶子节点使用双向链表串起来之后，就可以进行范围查找了；等值查找的时间复杂度还是树高O(logn)；看上去还不错，但是实际使用时有问题，因为我们数据库中需要存储的数据实在是非常多，如果使用这样的改造后的二叉树，树的高度将是非常惊人的。不但查找起来非常缓慢，而且这么多节点全部加载到内存中也是不现实的。
我们再次进行如下的改造：
只把所有索引树的根节点放入到内存中，其它子节点都放到磁盘上；将二叉树改造为m叉树，每个节点的子节点个数最多为m个，如此树的高度就大大降低了，减少了IO磁盘查找的次数；每个子节点的大小不能超过一页的大小，通常为4kb，保证m最大的同时，OS单次读页就能将该节点加载完毕；改造后的数据结构示意图如下：
改造后的好处是：
没有把索引树的全部节点加载到内存，减少了内存的压力；m叉树使得索引树的高度尽可能降低了，减少了IO查找节点的次数，提高了时间效率；m取值有了理论依据，使得时间效率最大化；但同时也有部分缺点：
数据的写入和删除都会导致索引的更新，从而需要更改索引树；当插入数据的时候，如果某个节点的子节点个数超过m，就需要分裂，极端情况下，需要从下往上传导分裂；当删除数据的时候，如果某个节点的个数小于m/2，则需要合并节点，否则这样的节点多了，影响查询效率； 三、B+树总结 每个节点中的子节点个数不能超过m，不能小于m/2；根节点的子节点个数可以小于m/2，但是不能超过m；每个节点只存储索引，并不存储数据；所有叶子节点都是双链表串联的，方便范围查找；根节点会被存储在内存中，其它节点存储在磁盘中； 四、和B树的关系B+树是在B树的基础上改进的，B树中每个节点是存储真实的数据的，所以整个树会很大；B树的叶子节点是没有用链表串联的，所以还是无法满足范围查找的场景；因此，B树其实就是一个子节点不能小于m/2的m叉树；
B+树和B树的关系，以及MySQL中不同存储引擎数据结构的不同可以参考《【数据库专题】如何理解数据库的索引？》
 1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |
标签： #数据库专题一文搞懂
