红黑、B、B+

二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

平衡二叉树

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：

是一棵空树或左右子树的高度差绝对值不超过1，且左右子树都是一棵平衡二叉树，

平衡二叉树必定是二叉搜索树，反之则不一定。

一般的二叉搜索树，期望高度（即为一棵平衡树时）为log2n，各操作的时间复杂度（O(log2n)）也由此而决定。但在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但在进行多次操作后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。

在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。

2-3-4树

在二叉树中，每个节点有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。2-3-4树就是多叉树，它的每个节点最多有四个子节点和三个数据项。

2-3-4树和红黑树一样是平衡树。它的效率比红黑树稍差，但编程容易。通过2-3-4树可以更容易地理解B-树。

B-树是另一种多叉树，专门用在外部存储中来组织数据。B-树中的节点可以有几十或几百个子节点。

2-3-4树名字中的2,3,4的含义是指一个节点可能含有的子节点的个数。对非叶子节点有三种可能的情况：

有一个数据项的节点总是有两个子节点：sub1<data1<sub2
有两个数据项的节点总是有三个子节点：sub1<data1<sub2<data2<sub3
有三个数据项的节点总是有四个子节点：sub1<data1<sub2<data2<sub3<data3<sub4

2-3-4树中所有叶结点总是在同一层，即叶子节点到根节点长度相同

查询：比较数值，递归查找

插入：比较查找范围，然后2节点变3节点，3节点表4节点。4节点情况需要将当前节点的中间节点上移一层到父节点。为了避免父节点也是4节点，需要控制4节点只会出现在最后一层。

红黑树

典型的应用是实现关联数组、java中的TreeMap、TreeSet以及HashMap。关联数组不是顺序存储，不仅可以通过整数来索引，还可以使用字符串或其他类型的值来索引。

红黑树（Red Black Tree）是一种自平衡二叉查找树，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。虽然复杂，但最坏情况运行时间良好：它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

有5个性质：

节点是红色或黑色。
根节点是黑色。
每个叶节点（NIL节点，空节点）是黑色的。
每个红色节点的两个子节点都是黑色。(即每个叶子到根的路径不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的

注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也是二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更，并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次，但是它导致了非常复杂的操作。

插入时可能会破坏红黑树的特性，需要进行调整，有两种策略：变色和旋转。

插入一次可能需要同时进行多次的变色和旋转。（旋转还分为左旋转右旋转）

B树

每个结点至多拥有m棵子树；
根结点至少拥有两颗子树（存在子树的情况下）；
除了根结点以外，其余每个分支结点至少拥有 m//2 棵子树；
所有的叶结点都在同一层上；
有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；

插入

新结点一般插在第h层，通过搜索找到对应的结点进行插入，那么根据即将插入的结点的数量又分为下面几种情况。

如果该结点的关键字个数没有到达m-1个，那么直接插入即可；
如果该结点的关键字个数已经到达了m-1个，那么根据B树的性质显然无法满足，需要将其进行分裂。分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。

删除

同样的，我们需要先通过搜索找到相应的值，存在则进行删除，需要考虑删除以后的情况，

如果该结点拥有关键字数量仍然满足B树性质，则不做任何处理；
如果该结点在删除关键字以后不满足B树的性质（关键字没有到达ceil(m/2)-1的数量），则需要向兄弟结点借关键字，这有分为兄弟结点的关键字数量是否足够的情况：
- 如果兄弟结点的关键字足够借给该结点，则过程为将父亲结点的关键字下移，兄弟结点的关键字上移；
- 如果兄弟结点的关键字在借出去以后也无法满足情况，即之前兄弟结点的关键字的数量为ceil(m/2)-1，借的一方的关键字数量为ceil(m/2)-2的情况，那么我们可以将该结点合并到兄弟结点中，合并之后的子结点数量少了一个，则需要将父亲结点的关键字下放，如果父亲结点不满足性质，则向上回溯；
  其余情况参照BST中的删除。

B+树

B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：

有n棵子树的结点含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。

所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

对比

为什么说B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引？

B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘块。而B+树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候，B 树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

B+树的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

具体应用

AVL树: 最早的平衡二叉树之一。windows对进程地址空间的管理用到了AVL树。
红黑树: 平衡二叉树，广泛用在C++的STL中。如map/set/multimap。还有Java中的HashMap、TreeSet、TreeMap以及关联数组。

简单来说都是用来搜索的。

AVL树：平衡二叉树，一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。

我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。这种情况优于红黑树。

红黑树，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。

B/B+树: 用在磁盘文件组织数据索引和数据库索引。新的值可以插在已有的节点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。

多路查找树，因为分支多层数少，适用于数据库系统。磁盘IO是非常耗时的，而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。能保持log(n)的插入与查询

B+树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。

B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可。B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序扫，所以B+树更加适合在区间查询的情况。

Trie树(字典树): 用在统计和排序大量字符串，如自动机。