数据库索引为什么使用 B+ 树

原文：https://blog.csdn.net/Lucky666666666666/article/details/105038976

为什么不是 hash 索引

1. hash 表只能匹配是否相等，不能实现范围查找，因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索。

2. 当需要按照索引进行 orderby 的时候，hash 值没办法支持排序，因为 hash 散列的特性，无法利用索引完成排序。

3. 组合索引可以支持部分索引查询，如（a，b，c）的组合索引，查询中只用到了 a 和 b 也可以查询，如果使用 hash 表，组合索引会将几个字段合并 hash，没办法支持部分索引。

4. 当数据量很大的时候，hash 冲突的概率也很大，特别是在有大量重复键值的情况下，哈希索引的效率是非常低的，因为存在哈希碰撞问题。

为什么不选择红黑树

1. B 树相对于红黑树而言更偏胖矮，红黑树这种结构，h 很深，而 I/0 次数和 h 有关，h 越深，相对应的 I/0 次数越多，执行效率就越低。

2. 数据库系统的设计设巧妙用了磁盘预读的原理，将一个节点的大小设置为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入，而且由于逻辑上很近的节点在物理上可能很远（因为红黑树在物理存储上是一个数组的形式），假设当前节点在位置 i,那么他的左子节点在位置 2 * i，右子节点在位置 2 * i+1，当 i 很大的话，那么根节点虽然在逻辑上与其子节点相差很近，但是实际在物理上相差很远，因此载入内存的时候无法利用局部性原理，效率比 B-Tree 要差很多。

为什么不选择 B 树

1. B+树的内部结点并没有指向关键字具体信息的指针。而是指向叶子节点中关键字的索引，所以节点所占用的空间就小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多，相对来说 IO 读写次数也就降低了。

2. 非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当，查找性能也就越稳定。

3. B+树只要遍历叶子节点就可以实现整棵树的遍历，而且在数据库中基于范围的查询是非常频繁的，而 B 树只能中序遍历所有节点，效率太低。

4. B+树方便扫库，然而 B 树必须用中序遍历的方法按序扫库，而 B+树直接从叶子结点挨个扫一遍就完了，B+树支持 range-query 非常方便，而 B 树不支持，这是数据库选用 B+树的最主要原因。