SQL 05 - B树

B树

B树

B树即是balance tree, 二叉搜索树.

1. 所有非叶子节点至多拥有两个儿子.
2. 所有节点存储一个关键字.
3. 所有非叶子节点的左指针指向小于其关键字的子树, 右指针指向大于其关键字的子树.

B树在多次插入删除后, 复杂度有可能会退化, 最终退化到线性时间复杂度, 因此, 需要通过类似AVL树算法对B树进行维护.

B-树

B-树是一种平衡的多路查找树, B-树的所有节点的孩子节点数最大值称为B-数的阶, 用m表示. 一个节点有k个子节点, 那么自身有k-1个关键字.

1. 树中每个节点最多有m个子节点
2. 若根节点不是叶节点, 那么至少有两个子节点.
3. 除根节点外, 所有非叶节点至少有ceil(m/2)个子节点.

B-树中, 元素的添加删除可能会导致节点的拆分合并. B-树通过约束所有叶子节点在相同深度来保持平衡. 深度在元素添加至树的过程中缓慢增长, 而整体深度极少的增长.

B+树

B+树和B-树类似, 但是有几点不同:

1. 非叶节点的子节点个数与关键字个数相同.
2. 非叶节点的子节点指针P[i], 指向关键字属于[P[i], P[i+1])的子节点, 而B树两边都是开区间.
3. 为所有叶节点增加一个向后的指针, 使得其成为一个关键字有序的链表.
4. 所有的关键字都在叶节点出现. 非叶节点相当于是叶节点的索引, 叶节点相当于是存储数据的数据层.

B-树与B+树的区别

1. 非叶节点的关键字个数不同, B+树非叶节点有m个关键字, 其子节点也有m个. B-树有m个子节点的情况下, 当前节点的关键字个数为m-1.
2. 节点的数据类型不同. B-树的非叶节点保存数据和子节点的指针. B+数只有叶节点存储数据. 因此在遍历具体数据的时候, B+树只要按照链表遍历, 而B-树需要在树上进行中序遍历. 所以B+树常用于数据库索引, 因为在区间查询的情况下更高效, 而B-树常用于文件索引.

B+树相较于红黑树的优势

1. 更少的查找次数 平衡树查找的时间复杂度等于树的平均深度, 深度为以节点出度为底, 节点个数的对数. 红黑树的出度相较于B+要小很多, 所以深度也远大于B+数, 因此查找次数也多.
2. 利用计算机预读特性 为了减少磁盘I/O, 磁盘往往不是严格读取, 而是会进行预读, 用以利用局部性原理. 在预读过程中, 磁盘进行顺序读取, 这不需要进行磁盘寻道, 只需要很短的旋转时间. 操作系统一般将内存和磁盘分割成固定大小的快, 每一块成为一页, 这是磁盘和内存交换的单元. 数据库将索引的一个节点大小设置为页的大小, 使得一次I/O就能完全载入一个节点, 并且利用预读特性, 相邻节点也可以被预先加载.