浅谈【树】：红黑树、AVL树、B树、B+树

一、红黑树（漫画理解）

（PS:标题 超链接着漫画版的解读，看漫画，学数据结构，轻松get知识点~...）

1.1 二叉查找树

• 某节点的左子树节点值仅包含小于该节点值

• 某节点的右子树节点值仅包含大于该节点值

• 左右子树每个也必须是二叉查找树

1.2 红黑树

一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

1. 红黑树限制规则

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

• 1.节点是红色或黑色。

• 2.根节点是黑色。(黑土地孕育黑树根)

• 3.每个叶子节点都是黑色的空节点（NIL节点）。

• 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

• 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2. 调整规则

先试变色再试旋转（左旋或右旋）

3. 优点

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间

4. 用途

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是 O(lgn)，效率非常之高。

例如，Java 集合中的 TreeSet 和 TreeMap，C++ STL 中的 set、map，以及 Linux 虚拟内存的管理，都是通过红黑树去实现的。

---

二、树的深度优先遍历和广度优先遍历（漫画解读）

【简介】深度优先遍历简称DFS(Depth First Search)，广度优先遍历简称BFS(Breadth First Search)，它们是遍历图当中所有顶点的两种方式。

2.1 深度优先遍历

• 深度优先遍历，相当于你在游乐场游玩景点时，一头扎到底的玩法。我们选择一条支路，尽可能不断地深入，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入。

• 像这样先深入探索，走到头再回退寻找其他出路的遍历方式，就叫做深度优先遍历(DFS)。

• 其实二叉树的前序、中序、后序遍历，本质上可以认为是深度优先遍历。

• 算法实现的关键在于回溯，利用栈先进后出的特性或递归来实现（递归本质上是基于方法调用栈来实现）。

• 回溯：顾名思义，就是自后向前，追溯曾经走过的路径。

2.2 广度优先遍历

• 广度优先遍历，相当于在游乐场首先把起点相邻的几个景点玩遍，然后去玩距离起点稍远一些（隔一层）的景点，然后再去玩距离起点更远一些（隔两层）的景点......

• 像这样一层一层由内而外的遍历方式，就叫做广度优先遍历(BFS)。

• 其实二叉树的层序遍历本质上也可以认为是广度优先遍历

• 算法实现的关键在于重放，可以利用队列先进先出特性来实现

• 重放：与回溯完全相反，把遍历过的顶点按照之前的遍历顺序重新回顾，就叫做重放

三、B-树 和 B+树

【简单介绍】：动态查找树主要包括：二叉查找树，平衡二叉树，红黑树，B树，B+树，查找的时间复杂度就为O(log2N)，通过对数就可以发现降低树的深度就会提高查找效率。因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。在大数据存储过程，大量的数据会存储到外存磁盘，外存磁盘中读取与写入某数据的时候，首先定位到磁盘中的某一块，这就有个问题：如何才能有效的查找磁盘中的数据呢，这就需要一种高效的外存数据结构，B树就是为了提高磁盘或外部存储设备查找效率而产生的一种多路平衡查找树。

3.1 B树

【简介】：B树：（Balance Tree）即为平衡树的意思，为了存储设备或者磁盘而设计的一种多路平衡查找树，每个节点拥有更多的子节点，子节点的个数一般称为阶。

【备注一条】：在数据库索引中，没有B-树(B减树)的说法，这就是B树 ！！！

用途：

主要用于 文件系统以及部分数据库索引（比如：MongoDB菲关系型数据库）

B树 特性

一棵m阶的B树，特性如下：

• 每个节点至多m课子树。

• 根结点至少有两个子女。

• 除根节点外，其他节点至少[ceil(m / 2)（代表是取上限的函数）]课子树

• 根节点至少两颗子树

• 所有叶节点均在同一层上，B树叶节点不包含任何信息可以看成一种外部结点

• 有 j 个孩子的非叶结点恰好有 j-1 个关键码，关键码按递增次序排列

3.2 B+树

B+树的特点

• 1、有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

• 2、所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接（每一个叶子节点都带有指向下一节点的指针）。

• 3、所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。（最大元素在根节点）

• 4、如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。

---

【B树】 VS 【B+树】

B+树优于B树的几点内容：

• 1、【IO次数更少】单一节点存储更多的元素，相同数据量时，比B树“矮胖”（查询时，IO操作少，性能更优）

• 2、【查询性能稳定】 B+ 树每一次查找都到叶子节点，性能稳定；B树最好情况为只查根节点，最坏为查到叶子节点。

• 3、【范围查询简便】 叶子节点形成有序链表，B+树范围查询时只需在链表上遍历即可。

---

3.3 以上几种树在检索过程中的性能对比

如果在内存中红黑树比B树效率更高，一旦涉及磁盘操作B树就更好，B+树当然比B树更优。

索引在 MySQL 数据库中分三类：

• B+ 树索引

• Hash 索引

• 全文索引

• hash索引查找时间复杂度为O(1)，如果只选一条数据，hash索引更优，但数据库常选多条数据，这时由于B+有序且链表相连，查询效率更高。

• 数据库的索引一般存在磁盘上，数据量较大无法一次加载进内存时，B+树允许分批加载，同时树的高度较低，提高了查找效率。

---

（PS:标题 题干连接着漫画版的解读，看漫画，学数据结构，轻松get知识点~）

本文转载自：【陈小陌博客】：http://www.mylwx.cn/post/186.html