2022-09-20数据结构00
请注意,本文编写于 555 天前,最后修改于 555 天前,其中某些信息可能已经过时。

B-树

B-树主要用于文件系统以及部分数据库索引,如 MongoDB。使用 B-树来作为数据库的索引主要是为了减少查找是磁盘的 I/O 次数。试想,如果我们使用二叉查找树来作为索引,那么查找次数的最坏情况等于二叉查找树的高度,由于索引存储在磁盘中,我们每次都只能加载对应索引的磁盘页进入内存中比较,那么磁盘的 I/O 次数就等于索引树的高度。所以采用一种办法来减少索引树的高度是提高索引效率的关键。

B-树是一种多路平衡查找树,它的每一个节点最多包含 K 个子节点,K 被称为 B-树的阶,K 的大小取决于磁盘页的大小。每个节点中的元素从小到大排列,节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。简单来说就是以前一个磁盘页只存储一个索引的值,但 B-树中一个磁盘页中存储了多个索引的值,因此在相同的比较范围内,B-树相对于一般的二叉查找树的高度更小。其实它的主要目的就是每次尽可能多的将索引值加载入内存中进行比较,以此来减少磁盘的 I/O 次数,其实就查找次数而言,和二叉查找树比较差不了多少,只是说这个比较过程是在内存中完成的,速度更快而已。

详细资料可以参考: 《漫画:什么是 B- 树?》

本文作者:前端小毛

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!