B-树

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

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