数据库使用 B+ 树是怎么节省 IO 次数的呢？

这里的 IO，是指的读取外存（硬盘）的次数。

数据库使用树做索引是因为可以范围查找，而搜索树中， IO 的次数跟树的高度相关，为什么这么说呢？

通常树中的一个节点大小和数据库中的 page 大小存在关联， 而数据库是按 page 读取数据的，可以简单理解，数据库可以一次 IO 读取一个节点的数据。在搜索树的查找中， 要查询多少个节点就是多少次 IO， 为 log(h), h 是树的高度。

由于 page 的大小有限，我们希望每个节点，可以多存储一些 key （分割点）的个数， 节点中的 key 多了， 代表子树可以有更多的分支， 这就会降低树的高度。B 树中节点不仅保存了 key 还保存了节点的 Value ， 而 B+ 树中非叶子节点只保存 key， 所以能存储更多的 key。

如此这样减少高度， 减少 IO 次数。

另外，B+树的叶子节点形成了一个有序链表，这使得范围查询变得更加高效，因为可以顺着叶子节点的链表进行遍历，而不需要回溯非叶子节点。