学习笔记 | 红黑树、B-树、B+树
二叉查找树BST、红黑树、B-树、B+树
01 二叉查找树BST（又称二叉排序树）的特性
- 左子树上所有结点的值均小于或等于它的根结点的值。
- 右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
二叉查找树多次插入新结点会导致不平衡现象。
02 红黑树的特性和优势，在什么情况下需要变色、什么情况下需要旋转？
红黑树Red Black Tree是一种自平衡的二叉查找树。
- 结点是红色或黑色。
- 根结点是黑色。
- 每个叶子节点都是黑色的空结点（NIL结点）。
- 每个红色结点的两个子结点都是黑色。
（从每个叶子到根的所有路径上不能有两个连续的红色结点）。 - 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
- 正是因为这些规则限制，才保证了红黑树的自平衡。
- 红黑树从根到叶子的最长路径不会超过最短路径的2倍。
- 当插入或删除结点的时候，红黑树的规则有可能被打破。这时候就需要做出一些调整，来接续维持我们的规则。
变色
- 为了重新符合红黑树的规则，尝试把红色结点变为黑色，或者把黑色结点变为红色。
左旋转
右旋转
03 B-树 Balance Tree
Mysql里的索引是基于什么数据结构？
- 索引主要是基于Hash表或者B+树。
B+树的实现细节是什么样的？B-树和B+树有什么区别？联合索引在B+树中如何存储？
- B-树就是B树，中间的横线并不是减号。
- B树的一大优势：自平衡。
数据库索引为什么要使用树结构存储呢？
- 数据库的索引是存储在磁盘上的，当数据量比较大的时候，索引的大小可能有几个G甚至更多。能做的只有逐一加载每个磁盘页对应着索引树的节点。
- 磁盘的IO次数等于索引树的高度。
- 为了减少磁盘IO次数，我们需要把原本“瘦高”的树结构变得“矮胖”。这就是B-树的特征之一。
-
B-树是一种多路平衡查找树，它的每一个结点最多包含k个孩子，k被称为B树的阶。k的大小取决于磁盘页的大小。
一个m阶的B树具有如下几个特征：
1. 根结点至少有两个子女。
2. 每个中间结点都包含k-1个元素和k个孩子，其中m/2 <= k <= m。
3. 每一个叶子结点都包含k-1个元素，其中m/2 <= k <= m。
4. 所有的叶子结点都位于同一层。
5. 每个结点中的元素从小到大排列，结点当中k-1个元素正好是k个孩子包含的元素的值域分划。
- B-树主要应用于文件系统以及部分数据库索引，比如著名的非关系型数据库MongoDB。
- 而大部分关系型数据库，比如Mysql则使用B+树作为索引。
04 B+树 Balance Tree
- B+树是基于B-树的一种变体，有这比B-树更高的查询性能。
一个m阶的B+树具有如下几个特征：
1. 有k个子树的中间结点包含有k个元素。（B-树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3. 所有的中间结点元素都同时存在于子结点，在子结点元素中是最大(或最小)元素。
B+树的优势：
- 单一节点存储更多的元素，使得查询的IO次数更少。
- 所有查询都要查找到叶子节点，查询性能稳定。
- 所有叶子节点形成有序链表，便于范围查询。