B树，B+树

B树

2022-03-22 hw

Oyyko

B树和B+树的区别，B+树应用在哪?

B树是一种多路平衡查找树。B树允许每个节点有多个子节点。

B树里面，索引和数据在内存中相邻，称为一组键值对。而一个B树的节点，由多组键值对组成。

B树有一个参数m，参数为m的B树可以称为m阶B树。

其中：

每个节点最多有m-1个键值对

根节点最少有1个键值对

非根节点最少有m/2个键值对

每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。

所有叶子节点都位于同一层。

B+树与B树的相同点：

• 根节点至少一个元素
• 非根节点元素范围：m/2 <= k <= m-1

不同点：B+树中的数据只分布在叶子节点上。

B+树中有两种节点，索引节点和叶子节点。索引节点不存储数据，只存储索引。

内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

父节点存有右孩子的第一个元素的索引，用于进行比较查找。

B树不方便遍历所有元素，而B+树因为所有的叶子节点可以构成一个有序链表，因此能够快速方便的遍历所有元素。

B+树所有叶子节点构成有序链表还方便了我们进行区间查找，例如找出所有关键字大于50且小于300的元素。那么B+树里面我们可以找出边界，然后沿着链表遍历即可得到所有元素。

B+树所有的查询都要到叶子节点才终止，性能比较稳定。而B树可以提前查到，因此不稳定。

由于B+树不将数据信息存放进索引节点，也就是说节点信息的容量变小，那么一次性可以放进内存的节点数变多，意味着I/O操作变少，以此提高性能。

MYSQL使用B+树作为索引。文件系统中也使用B+树作为文件系统的索引。