B树、B+树、AVL树、Trie树及其应用场景

1. 应用场景

AVL树：平衡二叉树之一，应用相对其他数据结构比较少，windows对进程地址空间的管理用到了AVL

红黑树：平衡二叉树，广泛应用在C++STL中，比如map和set，Java的TreeMap

B和B+树：主要用在文件系统以及数据库中做索引等

Trie 树：用在统计和排序大量字符串中，一个典型应用是前缀匹配，比如下面这个很常见的场景，在我们输入时，搜索引擎会给予提示。还有比如IP选路，也是前缀匹配

R树：空间数据库索引

2. 二叉搜索树

不必多说了，可以参考 【九章算法基础班】二叉树与分治法

时间复杂度最好情况是$O(logn)$ ，最坏情况下时间复杂度$O(n)$，恰好选择了最小或者最大的节点做root，节点排在了一条直线上。

3. AVL树

AVL树是二叉搜索树的改进

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

上图是一个普通的平衡二叉树，这张图我们可以看出，任意节点的左右子树的平衡因子差值都不会大于1。

局限性：

由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。

4. 红黑树

4.1 简介

一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是弱平衡，可以推出，相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索、插入、删除操作较多的情况下，我们就用红黑树。

4.2 性质

1、每个节点非红即黑；

2、根节点是黑的；

3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；

4、如果一个节点是红的,那么它的两儿子都是黑的；

5、对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；

6、高度始终保持在h = logn

7、红黑树的查找、插入、删除的时间复杂度最坏为O(log n)

如下图所示，即是一颗红黑树(下图引自wikipedia：http://t.cn/hgvH1l)：

上文中我们所说的 “叶结点” 或”NULL结点”，它不包含数据而只充当树在此结束的指示，这些结点以及它们的父结点，在绘图中都会经常被省略。

4.3 应用

1、广泛用于C++的STL中，Map和Set都是用红黑树实现的；

2、著名的Linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；

3、IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查；

4、Nginx中用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；

5、Java中TreeMap的实现；

详细的插入、删除、旋转等操作可以参考：

面试旧敌之红黑树（直白介绍深入理解）

5. B树

5.1 B-树简介

B树是为实现高效的磁盘存取而设计的多叉平衡搜索树。这个概念在文件系统，数据库系统中非常重要。

​ B树是一种查找树，我们知道，这一类树（比如二叉查找树，红黑树等等）最初生成的目的都是为了解决某种系统中，查找效率低的问题。B树也是如此，它最初启发于二叉查找树，二叉查找树的特点是每个非叶节点都只有两个孩子节点。然而这种做法会导致当数据量非常大时，二叉查找树的深度过深，搜索算法自根节点向下搜索时，需要访问的节点也就变的相当多。如果这些节点存储在外存储器中，每访问一个节点，相当于就是进行了一次I/O操作，随着树高度的增加，频繁的I/O操作一定会降低查询的效率。

​ 这里有一个基本的概念，就是说我们从外存储器中读取信息的步骤，简单来分，大致有两步：

1. 找到存储这个数据所对应的磁盘页面，这个过程是机械化的过程，需要依靠磁臂的转动，找到对应磁道，所以耗时长。
2. 读取数据进内存，并实施运算，这是电子化的过程，相当快。

总的来说，B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉，B树每个内节点有多个分支)，与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，在关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少。而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

5.2 B-树结构

B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。

B树的结构要求：
1）根节点至少有两个子节点
2）每个节点有M-1个key，并且以升序排列
3）位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
4）其它节点至少有M/2个子节点 [M/2,M-1]
5）所有叶子节点都在同一层

B树高度

对于一个包含n个关键字，最小度数t≥2t≥2 的B树，其高度hh 一定满足：

$$h \leq \log_{t}{\frac{n + 1}{2}}$$

在搜索B树时，很明显，访问节点（即读取磁盘）的次数与树的高度呈正比，而B树与红黑树和普通的二叉查找树相比，虽然高度都是对数数量级，但是显然B树中log函数的底可以比2更大，因此，和二叉树相比，极大地减少了磁盘读取的次数。

5.3 B-树操作

1. 查找

   一棵已经建立好的B树如下图所示，我们的目的是查找关键字为29的文件：

   

   先简单说明一下上图：

   • 图中小红方块表示对应关键字锁代表的文件存储位置。实际上可以看做一个地址。比如根节点17旁边的小红块表示关键字17所对应的文件在硬盘中的存储地址。
   • P是指针。需要注意的是：指针 + 关键字 + 小红块 这三个东西合起来构成了一个B树的节点。这个节点存储在一个磁盘块上。

   下面看看搜索关键字29的文件的过程：

   1. 从根节点开始，读取根节点信息，根节点有2个关键字：17和35。因为17 < 29 < 35，所以找到指针P2指向的子树，也就是磁盘块3（1次I/0操作）
   2. 读取当前节点信息，当前节点有2个关键字：26和30。26 < 29 < 30，找到指针P2指向的子树，也就是磁盘块8（2次I/0操作）
   3. 读取当前节点信息，当前节点有2个关键字：28和29。找到了！（3次I/0操作）

   由上面的过程可见，同样的操作，如果使用平衡二叉树，那么需要至少4次I/O操作，B树比之二叉树的这种优势，还会随着节点数的增加而增加。另外，因为B树节点中的关键字都是排序好的，所以，在节点中的信息被读入内存之后，可以采用二分查找这种快速的查找方式，更进一步减少了读入内存之后的计算时间，由此更能说明对于外存数据结构来说，I/O次数是其查找信息中最大的时间消耗，而我们要做的所有努力就是尽量在搜索过程中减少I/O操作的次数。

2. 插入

   ​ 向B树种插入关键字的过程与向二叉查找树中插入关键字的过程类似，但是要稍微复杂一点，因为根据上面B树的定义，我们可以看出，B树每个节点中关键字的个数是有范围要求的，同时，B树是平衡的，所以，如果像二叉查找树那样，直接找到相关的叶子，插入关键字，有可能会导致B树的结构发生变化而这种变化会使得B树不再是B树。

   ​ 所以，我们这样来设计B树种对新关键字的插入：首先找到要插入的关键字应该插入的叶子节点（为方便描述，设这个叶子节点为u），如果u是满的（恰好有2t−1个关键字），那么由于不能将一个关键字插入满的节点，我们需要对u按其当前排在中间关键字$u.key_t$进行分裂，分裂成两个节点u1,u2；同时，作为分裂标准的关键字$u.key_t$被上移到u的父节点中，在$u.key_t$插入前，如果u的父节点未满，则直接插入即可；如果u的父节点已满，则按照上面的方法对u的父节点分裂，这个过程如果一直不停止的话，最终会导致B树的根节点分裂，B树的高度增加一层。

   ​ 下面用《算法导论》中的一个题目展示一下这种插入关键字的过程。

   现在我们要将关键字序列：F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y依次插入一棵最小度为2的B树中。也就是说，这棵树的节点中，最多有3个关键字，最少有1个关键字。

   第1步，F, S, Q可以被插入一个节点（也就是根节点）

   

   第2步，插入关键字K，因为节点已满，所以在插入前，发生分裂，中间关键字Q上移，建立了一个新的根节点：

   

   第3步，插入关键字C:

   

   第4步，插入关键字L，L应该被插入到根节点的左侧的孩子中，因为此时该节点已满，所以在插入前，发生分裂：

   

   第5步，插入关键字H, T, V，这个过程没有发生节点的分裂：

   

   第6步，插入关键字W，W应该被插入到根节点的最右侧的孩子中，因为此时该节点已满，所以在插入前，关键字T上移，最右端的叶子节点发生分裂：

   

   第7步，插入关键字M，M应该被插入到根节点的左起第2个孩子中，因为此时该节点已满，所以在插入前，发生分裂，分裂之后，中间关键字K上移，导致根节点发生分裂，树高增加1：

   

   第8步，同样的道理，插入关键字R, N, P, A, B, X, Y：最终得到的B树如下：

   

3. 删除

   ​ 删除操作的基本思想和插入操作是一样的，都是不能因为关键字的改变而改变B树的结构。插入操作主要防止的是某个节点中关键字的个数太多，所以采用了分裂；删除则是要防止某个节点中，因删除了关键字而导致这个节点的关键字个数太少，所以采用了合并操作。

   下面分三种情况来讨论下删除操作是如何工作的，这个过程的顺序是自根节点起向下遍历B树

   Case - 1：如果要删除的关键字k在节点u中，而且u是叶子节点，那么直接删除k

   Case - 2：如果要删除的关键字k在节点u中，而且u是内部节点。由于关键字影响着子树的范围，因此不能随意删除。必须从子树中找到一个合适的数字来替代k才可以。需要分以下3种情况讨论：

   (1) 如果u中前于k的子节点u1中至少含有t个关键字，则找出k在以u1为根的子树中的前驱k′（前驱的意思是u1中比k小的关键字中最大的），然后在以u1为根的子树中删除k′，并在u中以k′替代k

   (2) 如果上面的条件(1)不成立，也就是说，前于k的子节点中关键字的个数小于t了，那么就去找后于k的子节点，记为u2。若u2中至少含有t个关键字，则找出k在以u2为根的子树中的后继k′(大于k的关键字中最小的)，然后在以u2为根的子树中删除k′，并在u中以k′替代k。可以看出（2）是（1）的一个对称过程

   (3) 如果u1,u2中的关键字个数都是t−1，则将k和u2合并后并入u1，这样u就失去了k和指向u2的指针，最后递归地从u1中删除k

   Case - 3：如果要删除的关键字k不在当前节点u中，而且u是内部节点（如果自上而下扫描到叶子都没有这个关键字的话，那就说明要删除的关键字根本就不存在，所以此处只考虑u是内部节点的情况），则首先确定包含k的u的子树，我们这里设为u.pi。如果u.pi中至少含有t个关键字，那么继续扫描，寻找下一个要被扫描的子树；如果u.pi中只含有t−1个关键字，则需要分下面两种情况进行操作：

   (1) 如果u.pi至少有一个相邻的兄弟比较“丰满”（即这个兄弟至少有t个关键字）。则将u中的一个关键字降至u.pi，同时令u.pi的最“丰满”的兄弟中升一个关键至u。然后继续扫描B树，寻找k

   (2) 如果u.pi的两个相邻的兄弟都不“丰满”（都只有t−1个关键字）。则令u.pi和其一个兄弟合并，再将u的一个关键字降至新合并的节点。使之成为该节点的中间关键字。

   举个例子

   1、初始状态
   

   2、删除元素H
   首先查找H，H在一个叶子结点中，且该叶子结点元素数目3 > 2
   移动K至原来H的位置，移动L至K的位置（也就是结点中删除元素后面的元素向前移动）
   

   3、删除T
   在中间结点中找到T，此时删了T后该节点关键字个数 1 < 2
   将W上移到T的位置，然后将原包含W的孩子结点中的W进行删除，这里恰好删除W后，该叶子结点中元素个数 > 2，无需进行合并操作
   

   4、删除R
   R所在叶子结点中元素数目为2，删除导致只有1个元素

   如果其某个相邻兄弟结点中比较丰满（元素个数 > [M/2] - 1），则可以向父结点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中

   在这个实例中，右相邻兄弟结点中比较丰满（3 > 2），所以先向父节点借一个元素W下移到该叶子结点中，代替原来S的位置，S前移；然后X在相邻右兄弟结点中上移到父结点中，最后在相邻右兄弟结点中删除X，后面元素前移。
   

   5、删除E
   删除后会导致很多问题，因为E所在的结点数目刚好达标，刚好满足最小元素个数（[M/2] - 1），而相邻的兄弟结点也是同样的情况，删除一个元素都不能满足条件
   所以需要该节点与某相邻兄弟结点进行合并操作：

   首先，移动父结点中的元素（该元素在两个需要合并的两个结点元素之间）下移到其子结点中；
   然后将这两个结点进行合并成一个结点。

   即，将父节点中的元素D下移到已经删除E而只有F的结点中，然后将含有D和F的结点和含有A,C的相邻兄弟结点进行合并成一个结点。
   
   此时G所在节点只有一个元素，不行。
   此时该结点的相邻兄弟又不丰满，只能与兄弟结点进行合并成一个结点，而根结点中的唯一元素M下移到子结点，这样，树的高度减少一层。
   

6. B+树

​ B+树是B树的一种变形，它更适合实际应用中操作系统的文件索引和数据库索引。定义如下：（为和大多资料保持一致，这里使用阶数m来定义B+树，而不像之前的B树中，使用的是最小度t来定义）

1. 每个内部节点的关键字个数为[m/2,m] 个。其中每个关键字对应一个子树；
2. 根节点要么没有子树，要么至少有2颗子树
3. 叶子节点包含了全部的关键字以及关键字指向文件的指针，且：
   1. 所有叶子节点中的关键字按大小顺序排列
   2. 相邻的叶子节点顺序链接（相当于是构成了一个顺序链表）
   3. 所有叶子节点在同一层
4. 所有分支节点的关键字都是对应子树中关键字的最大值

比如，下图就是一个非常典型的B+树的例子。

B+树和B树相比，主要的不同点在以下3项：

• 内部节点中，关键字的个数与其子树的个数相同，不像B树中，子树的个数总比关键字个数多1个
• 所有指向文件的关键字及其指针都在叶子节点中，不像B树，有的指向文件的关键字是在内部节点中。换句话说，B+树中，内部节点仅仅起到索引的作用
• 在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支

6. R树

6.1 R树的结构

​ R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。下图1是R树的一个简单实例：

在R树中存放的数据并不是原始数据，而是这些数据的最小边界矩形（MBR），空间对象的MBR被包含于R树的叶结点中。

R树满足如下的性质：

1) 根结点至少有两个子结点，除非它同时是叶子结点

2) 每一个叶子结点包含 m至M个索引项记录，通常， m=M/2。

3) 每一个非叶子节点拥有m至M个子节点，除非它是跟节点。

4) 所有叶子节点都位于同一层。

支持搜索、增加、删除等操作，可以自定义矩形的最大子节点数。

更详细的内容可以参考空间数据索引RTree（R树）完全解析及Java实现

7. 对比

7.1 B树和B+树的区别

​ B/B+树用在磁盘文件组织、数据索引和数据库索引中。其中B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引，因为：
1、B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

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

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

3、B树在元素遍历的时候效率较低

由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。在数据库中基于范围的查询相对频繁，所以此时B+树优于B树。

7.2 红黑树与B树区别

  一言而知就是树的深度较高，在磁盘I/O方面的表现不如B树。
  要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定。
  所以，在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。在这方面，B树表现相对优异，B树可以有多个子女，从几十到上千，可以降低树的高度。

7.3 AVL树和红黑树

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

1、红黑树和AVL树都能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。
2、由于设计，红黑树的任何不平衡都会在三次旋转之内解决。AVL树增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

在查找方面：
  红黑树的性质(最长路径长度不超过最短路径长度的2倍)，其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。
  AVL是严格平衡的二叉查找树（平衡因子不超过1）。查找过程中不会出现最差情况的单支树。因此查找效率最好，最坏情况都是O(logN)数量级的。

所以，综上：
  AVL比RBtree更加平衡，但是AVL的插入和删除会带来大量的旋转。 所以如果插入和删除比较多的情况，应该使用RBtree, 如果查询操作比较多，应该使用AVL。

AVL是一种高度平衡的二叉树，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。

参考文献

为什么MySQL数据库索引选择使用B+树