2024年1月

这里的 IO,是指的读取外存(硬盘)的次数。

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

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

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

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

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