二叉树的局限性
二分查找法是一种高效的数据检索方式，时间复杂度为 O(log2n)。如果用二叉树作为索引的话，会导致树变的非常高，增加磁盘I/O的次数，影响数据的查询时间，因此一个节点就不能只有2个节点，应该允许有M个节点
什么B树
B树的英文是Balance Tree。也就是平衡多路搜索树，它的高度远小于平衡二叉树的高度，在文件系统和数据库中的索引结构经常采用B树来实现。
一个M阶的B树有以下特性
- 根节点的儿子树数大于2
- 每个中间节点包含K-1个关键字和k个孩子，孩子的数量 = 关键字 +1
- 所有的叶子结点位于同一层
什么是B+树
B+树基于B树做的了改进，主流的数据库都支持B+树的索引方式，差异有以下几点
- 有k个孩子节点就有k个关键字
- 非叶子结点的关键字也会同时存在在子叶节点中，并且是在子叶结点中所有的关键字最大
- 非子叶节点只用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中
- 所有关键字都在叶子结点中出现，叶子节点构成了一个有序链表。
B+ 树和 B 树有个根本的差异在于，B+ 树的中间节点并不直接存储数据。这样的好处都有什么呢？
首先，B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。
其次，B+ 树的查询效率更高，这是因为通常 B+ 树比 B 树更矮胖（阶数更大，深度更低），查询所需要的磁盘 I/O 也会更少。同样的磁盘页大小，B+ 树可以存储更多的节点关键字。
不仅是对单个关键字的查询上，在查询范围上，B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中，并通过有序链表进行了链接。而在 B 树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。
网友评论