数据结构中的树
数据结构中的树有很多种，常见的树包括二叉树、自平衡二叉查找树和 B 树。
树的相关术语
- 节点的度：一个节点包含的子树的个数。
- 叶子节点或终端节点：度为 0 的节点。
- 树的度：树内度最大的节点的度。
- 高度：对于任意节点 n，n 的高度为从 n 到一个叶子节点的最长路径长，所有的叶子节点高度都为 0。
- 深度：对于任意节点 n，n 的深度为从根节点到 n 的唯一路径长，根的深度为 0。
- 节点的层次：从根节点开始，根为第一层，根的子节点为第二层，以此类推。
二叉查找树
二叉查找树又叫二叉搜索树、有序二叉树或者排序二叉树，它是指一棵空树或者具有下列性质：
- 若任意节点的左子树不为空，则左子树上所有节点的值均小于它根节点的值。
- 若任意节点的右子树不为空，则右子树上所有节点的值均大于它根节点的值。
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点。
二叉查找树利用二分查找的思想，其查找、插入和删除的平均时间复杂度为 O(logN)，其中 N 为节点个数。其实这里的时间复杂度就是树的高度，理想状态下的时间复杂度为 O(logN)，最坏的情况下，二叉查找树会退化成线性表，此时的时间复杂度为 O(N)。很多改进版的二叉查找树可以使树高维持在 O(logN)，从而使最坏情况下的时间复杂度仍为 O(logN)，比如 AVL 树、红黑树等。
AVL 树
AVL 树是最早被发明的自平衡二叉查找树，AVL 树的任意一个节点对应的两棵子树的最大高度差（或者叫做平衡因子，Balance Factor）为 1，因此它也被称为高度平衡树。AVL 树的查找、插入和删除在平均和最坏情况下的时间复杂度都为 O(logN)。插入和删除元素可能会使平衡因子大于 1，此时需要对树进行一次或者多次旋转，从而实现树的重新平衡。
插入和删除元素可能会引起树的失衡，可将情况分为四种。我们约定其中 Root 表示失衡树的根节点，Pivot 为旋转后重新平衡的树的根节点。
LL 型
LL 型，也就是左左型，失衡的原因可能是在 Pivot 的左子树上插入节点。调整过程为一次右旋，即以 Pivot 为轴心，Root 节点右旋成为 Pivot 的右子树，Root 的左子树由 Pivot 的右子树代替。
RR 型
RR 型，也就是右右型，失衡的原因可能是在 Pivot 的右子树上插入节点。调整过程为一次左旋，即以 Pivot 为轴心，Root 节点左旋称为 Pivot 的左子树，Root 的右子树由 Pivot 的左子树代替。
LR 型
LR 型，也就是左右型，失衡的原因可能是在 Pivot 的右子树上插入节点。调整过程为一次左旋加一次右旋，即以 Pivot 为轴心，Root 节点左旋成为 Pivot 的左子树，Root 的右子树由 Pivot 的左子树代替，这样就将 LR 型转换成了 LL 型，然后再按照 LL 型的方法右旋即可。
RL 型
RL 型，也就是右左型，失衡的原因可能是在 Pivot 的左子树上插入节点。调整过程为一次右旋加一次左旋，即以 Pivot 为轴心，Root 节点右旋成为 Pivot 的右子树，Root 的左子树由 Pivot 的右子树代替，这样就将 RL 型转成了 RR 型，然后再按照 RR 型的方法左旋即可。
AVL 树的局限性
由于维护这种高度平衡需要付出很大的代价，因此 AVL 的实际应用不多，更多的是采用追求局部而不是非常严格的整体平衡的红黑树。如果应用场景中插入和删除不频繁而查找频繁，那么 AVL 树还是优于红黑树的。
红黑树
红黑树是一种自平衡二叉查找树，与普通的二叉查找树不同的是，它的每个节点都带有颜色属性，颜色有红色或黑色两种。红黑树除了具有二叉查找树的性质外，还具有以下性质：
- 节点是黑色或者红色。
- 根是黑色的。
- 所有的叶子节点（实际上就是 NULL 指针）都是黑色的。
- 如果一个节点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色节点）。
- 从任意一个节点到其每个叶子节点的所有简单路径中都包含相同数目的黑色节点。
红黑树的数据项只能存储在内部节点（internal node）中，叶子节点在其父节点中仅仅作为一个 NULL 指针表示，将它也看作一个节点有助于描述红黑树的插入和删除算法。以上性质决定了从根节点到叶子节点的最长路径的长度不会超过任何其他路径长度的两倍。比如有一棵红黑树，它的根节点到叶子节点的路径中黑色节点数为 3，从根节点到叶子节点的最短路径长为 2（黑 - 黑 - 黑），那么最长路径也只可能为 4（黑 - 红 - 黑 - 红 -黑）。
一个拥有 N 个内部节点的红黑树的树高 $h <= 2log(N + 1)$。
红黑树与 AVL 树比较
红黑树并不追求高度平衡，即不像 AVL 树那样要求 $BF <= 1$，它只要求部分达到平衡，通过这种非严格的平衡来换取插入和删除节点时旋转次数的降低。在插入节点导致树失衡时，AVL 树和红黑树都可以通过最多两次旋转来实现树的重新平衡，旋转的时间复杂度为 O(1)。在删除节点导致树失衡时，AVL 树需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的时间复杂度为 O(logN)，而红黑树最多只需要 3 次旋转就可以实现树的重新平衡。
红黑树的查询性能稍逊于 AVL 树。在具有相同节点的情况下，红黑树的高度最多会比 AVL 树多 1。
B-树
B 树也表示为 B-树，是一种自平衡的树，概括来说，它是一种一般化的二叉查找树，一个节点可以拥有 2 个以上的子节点，因此又被称为平衡多路查找树。在 B 树中，查找、插入和删除等的时间复杂度都为 O(logN)。
当数据被插入或者从一个节点中移除，它的子节点的数量发生了变化，为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点的数量有一定的范围，所以 B 树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，所以可能浪费了一些空间。子节点数量的上界和下界依据特定的实现而设置，比如在一个 2-3 B 树（简称 2-3 树）中，每一个内部节点只能有 2 个或 3 个子节点。
B 树中每一个内部节点会包含一定数量的键，键将节点的子树分开。例如，如果一个内部节点有 3 个子节点（子树），那么它就必须有两个键：a1 和 a2。左子树的所有值都必须小于 a1，中间子树的所有值都必须在 a1 和 a2 之间，右子树的所有值都必须大于 a2。
通常，键的数量被选定在 d 和 2d 之间。其中 d 是键的最小数量，d + 1 是树最小的度或分支因子。在实际中，键值占用了节点中大部分的空间。因数 2 将保证节点可以被拆分或组合。如果一个内部节点有 2d 个键，那么要添加一个键值给此节点，只需要拆分这 2d + 1 个键为 2 个拥有 d 个键的节点，并把中间值节点移动到父节点。每一个拆分的节点需要拥有足够数目的键。相似地，如果一个内部节点和他的邻居两者都有 d 个键，那么将通过它与邻居的合并来删除一个键。删除此键将导致此节点拥有 d - 1 个键，与邻居的合并则加上 d 个键，再加上从邻居节点的父节点移来的一个键值，结果为完全填充的 2d 个键。
下面演示一个 B 树插入的例子，该 B 树为 3 阶，节点最多有 3 个孩子。
根据 Knuth 的定义，一个 m 阶（m 阶代表一个节点最多有 m 个查找路径，m = 2 是二叉树，m = 3 是三叉树）的 B 树是一个有以下属性的树：
- 每个节点最多有 m 个子节点。
- 每个非叶子节点（除根节点外）最少有
ceil(m/2)个子节点。 - 如果根节点不是叶子节点，那么它至少有 2 个子节点。
- 有 k 个子节点的非叶子节点拥有 k - 1 个键。
- 所有的叶子节点都在同一层。
AVL 树与 B-树比较
在多级存储系统（将多级存储器结合起来的系统，比如在计算机系统中，高速缓存、内存和硬盘就组成一个多级存储系统）中，在速度相对较慢的外部设备上存储数据可以使用 B 树，这在查找数据时将大大减少 I/O 次数。下面我们分析为什么使用 B 树，这里使用 AVL 树来作比较是因为它高度平衡，树高较矮。
假如有 $10^9$ 条数据，将它们插入到一棵 AVL 树中，那么树高大约为 $\log_2(10^9)\approx30$，这表示每次查找最多需要进行 30 次 I/O 操作，一次 I/O 操作只能读取一个值。
如果使用 B 树存储这些数据，我们可以充分利用外存的预读机制（一次 I/O 操作会读取一页或几页数据），将 B 树一个节点的大小设置为内存中一页的大小，这样一次 I/O 操作就可以读取到整个节点上的键值。每个节点上存储 m 个键，每个键除了存储键值，还需要存储数据和指针，因此 m 的计算公式大概为 m = pagesize/(keysize + datasize + pointsize)，假设求出 m 的值为 256，也就是说这是一棵 256 阶的 B 树，则每次查找最多只需要 $log(256,10^9) <= 4$ 次 I/O 操作。当定位到数据所在的节点后，接下来只需要在内存中查找即可（整个节点的数据都读到内存中了），相比磁盘 I/O 要快很多。
数据库使用 B 树作为索引结构的原因
数据库索引是存储在磁盘上的，当数据量比较大的时候，索引文件可能有几个 G 甚至更多，数据库利用索引进行查询的时候，肯定不能将整个索引文件读取加载到内存中，数据库能做的就是加载一部分数据到内存，如果使用普通的二叉查找树或者是自平衡二叉查找树，由于索引数量众多造成树高较高，同时查找数据时不能很好地利用磁盘的预读机制，造成 I/O 次数过多，从而影响效率。
数据库使用 B 树存储数据时，可以巧妙地利用磁盘预读机制，将一个节点的大小设置为一个内存页的大小，这样每个节点只需要一次 I/O 就可以完全加载到内存。在实际实现时，数据库每次新建节点都需要申请一个页的内存空间，这样就保证一个节点物理上也存储在一个页中，加上计算机存储分配时都是按页对齐的，这样就实现了一个节点只需要一次 I/O。
B-树一次检索的时间复杂度为 $log_mN$，其中 m 就是 B 树的阶，一般 m 是一个非常大的数字，通常是超过 100 的，因此 $log_mN$ 的值一般不超过 3。
B+树
B+树是 B-树的变体，它与 B-树的不同之处在于：
- 所有的键都会在叶子节点中出现。
- 内部节点不存储数据，叶子节点存储数据。
- 所有的叶子节点都有一个链指针，指向相邻叶子节点。
MySQL 的索引结构为什么使用 B+树
- 由于 B+树的内部节点不存储数据，所以单个节点可以存储更多的键，这也就意味着 B+树单次磁盘 I/O 能够获取到更多的键。
- 通常关系型数据库中，区间访问是很常见的，B+树的叶子节点增加了链指针，这样就增强了区间可访问性，可以实现区间范围的查询，而 B-树的每个节点都会存储 key 和 data，无法实现区间访问。