B树和B+树的对比

B树和B+树的对比

4阶指每个节点最多有4个子树。从查找效率考虑一般要求B树的阶数m >= 3。

每个元素不保存数据指针，只用来索引，所有数据都保存在叶子节点。
所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接（双向链表）。
所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定。而Ｂ＋树每次必须查找到叶子结点，性能稳定。
在范围查询方面，B+树的优势更加明显，因为叶子节点处有链表。
B+树单一节点存储更多的元素（因为中间节点不保存数据指针），这意味着同样的大小的磁盘页可以容纳更多节点元素（结点规模一般以一个磁盘页为单位），在相同的数据量下，Ｂ＋树更加“矮胖”，IO操作更少。

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有以下两个原因：

（一）更少的查找次数

平衡树查找操作的时间复杂度和树高 h 相关，O(h)=O(logdN)，其中 d 为每个节点的出度。

红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。

（二）利用磁盘预读特性

为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的旋转时间，速度会非常快。

操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入。

（三）范围查找更快
在范围查询方面，B+树的优势更加明显，因为叶子节点处有链表。而红黑树只能一个一个查找，M * logN （M是范围的大小）。