当前位置：首页 > news >正文

搜索树——AVL、红黑树、B树、B+树

news 来源：原创 2025/9/3 5:34:24

二叉搜索树

AVL树

2-3-4树

红黑树

旋转操作

概念讲解

旋转节点操作（左旋）

插入节点

删除节点

B树和B+树

B树

2.5.2 B+树

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

难度高，如果想要了解红黑树的增加、删除节点操作，一定要穷举画图理解！！！

二叉搜索树

一个二叉查找树是由n个节点随机构成,所以，对于某些情况,二叉查找树会退化成一个有n个节点的线性链。

BST存在的问题是，树在插入的时候会导致倾斜，不同的插入顺序会导致数的高度不一样，而树的高度直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上，这样树的高度为N。基于BST存在的问题，平衡查找二叉树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树（高度平衡树，具备二叉搜索树的全部特性，而且左右子树高度差不超过1）和红黑树。

AVL树

它的核心目标是通过动态调整树的结构，保持高度平衡，从而确保查找、插入和删除操作的时间复杂度始终为O(log n)，避免普通二叉搜索树在极端情况下退化成链表的低效问题。

但是AVL树要求太过严格，左旋和右旋的开销会比较大，这时出现了红黑树，只要求黑色节点平衡即可。

2-3-4树

2-3-4树是四阶的 B树(Balance Tree)，他属于一种多路查找树，它的结构有以下限制：所有叶子节点都拥有相同的深度。节点只能是 2-节点、3-节点、4-节点之一。

2-节点：包含 1 个元素的节点，有 2 个子节点；
3-节点：包含 2 个元素的节点，有 3 个子节点；
4-节点：包含 3 个元素的节点，有 4 个子节点；

所有节点必须至少包含1个元素元素始终保持排序顺序，整体上保持二叉查找树的性质，即父结点大于左子结点，小于右子结点；而且结点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。

生成2-3-4树简图

红黑树

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

每个节点要么是黑色，要么是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色。
每个红色结点的两个子结点一定都是黑色。
任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色

操作	描述
左旋	以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
右旋	以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
变色	结点的颜色由红变黑或由黑变红。

旋转操作

概念讲解

左旋：以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。

右旋：以某!个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。

旋转节点操作（左旋）

private void leftRotate(RBNode p){if(p != null){RBNode r = p.right;// 1.设置 pr-rl 要变为 p-rl// 把rl设置到p的右子节点p.right = r.left;if(r.left != null){// 设置rl的父节点为pr.left.parent = p;}// 2.判断p的父节点情况r.parent = p.parent; // 不管 p是否有父节点，都把这个父节点设置为 r的父节点if(p.parent == null){root = r; // p没有父节点 则r为root节点}else if(p.parent.left == p){p.parent.left = r; // 如果p为 p.parent的左子节点 则 r 也为 p.parent的左子节点}else{p.parent.right = r; // 反之设置 r 为 p.parent的右子节点}// 最后 设置 p 为 r 的左子节点r.left = p;p.parent = r;}}

/*** 围绕p右旋* @param p*/public void rightRotate(RBNode p){if(p != null){RBNode r = p.left;p.left = r.right;if(r.right != null){r.right.parent = p;}r.parent = p.parent;if(p.parent == null){root = r;}else if(p.parent.left == p){p.parent.left = r;}else{p.parent.right = r;}r.right = p;p.parent = r;}}

插入节点

/*** 新增节点* @param key* @param value*/public void put(K key , V value){RBNode t = this.root;if(t == null){// 说明之前没有元素，现在插入的元素是第一个root = new RBNode<>(key , value == null ? key : value,null);return ;}int cmp ;// 寻找插入位置// 定义一个双亲指针RBNode parent;if(key == null){throw new NullPointerException();}// 沿着跟节点找插入位置do{parent = t;cmp = key.compareTo((K)t.key);if(cmp < 0){// 左侧找t = t.left;}else if(cmp > 0){// 右侧找t = t.right;}else{// 插入节点的值==比较的节点。值替换t.setValue(value==null?key:value);return;}}while (t != null);// 找到了插入的位置  parent指向 t 的父节点  t为null// 创建要插入的节点RBNode<K, Object> e = new RBNode<>(key, value == null ? key : value, parent);// 然后判断要插入的位置 是 parent的 左侧还是右侧if(cmp < 0){parent.left = e;}else{parent.right = e;}// 调整  变色 旋转fixAfterPut(e);}


private boolean colorOf(RBNode node){return node == null ? BLACK:node.color;}private RBNode parentOf(RBNode node){return node != null ? node.parent:null;}private RBNode leftOf(RBNode node){return node != null ? node.left:null;}private RBNode rightOf(RBNode node){return node != null ? node.right:null;}private void setColor(RBNode node ,boolean color){if(node != null){node.setColor(color);}}/*** 插入节点后的调整处理* 1. 2-3-4树 新增元素 2节点添加一个元素将变为3节点 直接合并，节点中有两个元素*      红黑树：新增一个红色节点，这个红色节点会添加在黑色节点下(2节点) --- 这种情况不需要调整* 2. 2-3-4树 新增元素 3节点添加一个元素变为4节点合并 节点中有3个元素*      这里有6中情况，( 根左左 根左右  根右右 根右左)这四种要调整  (左中右的两种)不需要调整*      红黑树：新增红色节点 会添加到 上黑下红的节点中 = 排序后中间节点是黑色，两边节点是红色**  3. 2-3-4树：新增一个元素 4节点添加一个元素需要裂变：中间元素升级为父节点，新增元素与剩下的其中一个合并*      红黑树：新增节点是红色+爷爷节点是黑色，父亲节点和叔叔节点为红色 调整为*              爷爷节点变红色，父亲和叔叔节点变为黑色，如果爷爷节点为root节点则调整为黑色* @param x*/private void fixAfterPut(RBNode<K, Object> x) {x.color = RED;// 本质上就是父节点是黑色的就不需要调整，对应的 2 3的情况while(x != null && x != root && x.parent.color == RED){// 1. x 的父节点是爷爷的 左孩子if(parentOf(x) == parentOf(parentOf(x)).left){// 获取当前节点的叔叔节点RBNode y = rightOf(parentOf(parentOf(x)));// 情况3if(colorOf(y) == RED){// 说明是 上3的情况  变色处理// 父亲节点和叔叔节点设置为黑色setColor(parentOf(x),BLACK);setColor(y,BLACK);// 爷爷节点设置为 红色setColor(parentOf(parentOf(x)),RED);// 递归处理x = parentOf(parentOf(x));}else{// 情况 2if(x == parentOf(x).right){// 如果x是父节点的右节点那么我们需要先根据 父节点 左旋x = parentOf(x);leftRotate(x);}// 叔叔节点为空  对应于 上面的情况2// 将父节点变为黑色setColor(parentOf(x),BLACK);// 将爷爷节点变为红色setColor(parentOf(parentOf(x)),RED);// 右旋转  根据爷爷节点右旋转rightRotate(parentOf(parentOf(x)));}}else{// x 的父节点是爷爷是右孩子// 获取父亲的叔叔节点RBNode y = leftOf(parentOf(parentOf(x)));if(colorOf(y) == RED){// 情况3setColor(parentOf(x),BLACK);setColor(y,BLACK);setColor(parentOf(parentOf(x)),RED);x = parentOf(parentOf(x));}else{// 情况2if( x == parentOf(x).left){x = parentOf(x);rightRotate(x);}setColor(parentOf(x),BLACK);setColor(parentOf(parentOf(x)),RED);leftRotate(parentOf(parentOf(x)));}}}root.color = BLACK;}

删除节点

红黑树删除操作的本质其实就是删除2-3-4树的叶子节点

private RBNode getNode(K key){RBNode node = this.root;while (node != null ){int cmp = key.compareTo((K) node.key);if(cmp < 0){// 在左子树node = node.left;}else if(cmp >0){// 右子树node = node.right;}else{return node;}}return null;}


/*** 删除节点* @param key* @return*/public V remove(K key){// 先找到这个节点RBNode node = getNode(key);if(node == null){return null;}// 把值存起来 删除后 返回V oldValue = (V) node.value;deleteNode(node);return oldValue;}/*** 删除节点*   3种情况* 1.删除叶子节点，直接删除* 2.删除的节点有一个子节点，那么用子节点来替代* 3.如果删除的节点右两个子节点，此时需要找到前驱节点或者后继节点来替代*    可以转换为 1、2的情况* @param node*/private void deleteNode(RBNode node){// 3.node节点有两个子节点if(node.left !=null && node.right != null){// 找到要删除节点的后继节点RBNode successor = successor(node);// 然后用后继节点的信息覆盖掉 要删除节点的信息node.key = successor.key;node.value = successor.value;// 然后我们要删除的节点就变为了 后继节点node = successor;}// 2.删除有一个子节点的情况RBNode replacement = node.left != null ? node.left : node.right;if(replacement != null){// 替代者的父指针指向原来 node 的父节点replacement.parent = node.parent;if(node.parent == null){// 说明 node 是root节点root = replacement;}else if(node == node.parent.left){// 双向绑定node.parent.left = replacement;}else{node.parent.right = replacement;}// 将node的左右孩子指针和父指针都指向null node等待GCnode.left = node.right = node.parent = null;// 替换完成后需要调整平衡if(node.color == BLACK){// fixAfterRemove(replacement)}}else if(node.parent == null){// 说明要删除的是root节点root = null;}else{// 1. node节点是叶子节点 replacement为null// 先调整if(node.color == BLACK){// fixAfterRemove(node)}// 再删除if(node.parent != null){if(node == node.parent.left){node.parent.left = null;}else{node.parent.right = null;}node = null;}}}

B树和B+树

B树

（Balanced Tree）这个就是我们的多路平衡查找树，叫做B-Tree（B代表平衡）。跟AVL树一样，B树在枝节点和叶子节点存储键值、数据地址、节点引用。它有一个特点：分叉数（路数）永远比关键字数多1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。

B Tree的查找规则是什么样的呢？比如我们要在这张表里面查找15。因为15小于17，走左边。因为15大于12，走右边。在磁盘块7里面就找到了15，只用了3次IO。

这个是不是比AVL 树效率更高呢？那B Tree又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟AVL树有什么区别？比如Max Degree（路数）是3的时候，我们插入数据1、2、3，在插入3的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有4个指针，子节点会变成4路，所以这个时候必须进行分裂（其实就是B+Tree）。把中间的数据2提上去，把1和3变成2的子节点。如果删除节点，会有相反的合并的操作。注意这里是分裂和合并，跟AVL树的左旋和右旋是不一样的。我们继续插入4和5，B Tree又会出现分裂和合并的操作。

从这个里面我们也能看到，在更新索引的时候会有大量的索引的结构的调整，所以解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。节点的分裂和合并，其实就是InnoDB页（page）的分裂和合并。

相比AVL树，B树的树高更低，尤其适用于磁盘存储场景。由于B树每个节点可存储多个关键字（如Max Degree=3时，每个节点最多存2个关键字），能显著减少IO次数，提升大规模数据查询效率。

2.5.2 B+树

加强版多路平衡查找树因为B Tree的这种特性非常适合用于做索引的数据结构，所以很多文件系统和数据库的索引都是基于B Tree的。但是实际上，MySQL里面使用的是B Tree的改良版本，叫做B+Tree（加强版多路平衡查找树）。

B+树的存储结构：

MySQL中的B+Tree有几个特点：

它的关键字的数量是跟路数相等的；
B+Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。搜索到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索id=28，虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以还要继续往下搜索，一直到叶子节点。
B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。

总结， B+Tree的特点带来的优势：

它是B Tree的变种，B Tree能解决的问题，它都能解决。B Tree解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵B+Tree拿到所有的数据）
B+Tree的磁盘读写能力相对于B Tree来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
效率更加稳定（B+Tree永远是在叶子节点拿到数据，所以IO次数是稳定的）

二叉搜索树

AVL树

2-3-4树

红黑树

旋转操作

概念讲解

旋转节点操作（左旋）

插入节点

删除节点

B树和B+树

B树

2.5.2 B+树

相关文章：