为什么B+树索引比顺序索引文件效率要高?

一、为什么B+树索引比顺序索引文件效率要高

B+树进化具有的优点

索引节点没有数据，比较小，能够完全加载到内存中而且叶子节点之间都是链表的结构，所以B+Tree也是可以支持范围查询的，而B树每个节点key和data在一起，则无法区间查找B+树中因为数据都在叶子节点，每次查询的时间复杂度是稳定的，因此稳定性保证了

B+树的检索过程

我们再来看下B+树的检索过程

从B+树的根开始，逐层找到叶子节点。找到叶子节点为对应的数据页，将数据叶加载到内存中，通过页目录的槽采用二分查找的方式先找到一个粗略的记录分组。在分组中通过链表遍历的方式进行记录的查找。

B+树页节点结构

将所有的记录分成几个组，每组会存储多条记录，页目录存储的是槽（slot），槽相当于分组记录的索引，每个槽指针指向了不同组的最后一个记录我们通过槽定位到组，再查看组中的记录

页的主要作用是存储记录，在页中记录以单链表的形式进行存储。
单链表优点是插入、删除方便，缺点是检索效率不高，最坏的情况要遍历链表所有的节点。因此页目录中提供了二分查找的方式，来提高记录的检索效率。所以B+树索引比顺序索引文件效率要高。

延伸阅读：

二、为什么要从AVL树变成B树

因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。

但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。

另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。

如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。

如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。

我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？

可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低