在理解 B树、B+树、AVL树、红黑树 之前，咱们先看一下各种树型构造的大抵理论利用场景：

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

AVL树：均衡二叉树之一，利用绝对其余数据结构比拟少，windows对过程地址空间的治理用到了AVL

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

树结构曾经有了很多种形式，为何呈现 B树、B+树、AVL树、红黑树，首先要理解一下二叉搜寻树

  1. 二叉搜寻树

1）概念

均衡二叉树是采纳二分法思维把数据按规定组装成一个树形构造的数据，用这个树形构造的数据缩小无关数据的检索，大大的晋升了数据检索的速度。

咱们在二叉树的深度遍历过程中，应用中序遍历，就能获取失去有序的序列。

2）特点

  • 任意节点左子树不为空,则左子树的值均小于根节点的值.
  • 任意节点右子树不为空,则右子树的值均大于于根节点的值.
  • 任意节点的左右子树也别离是二叉查找树.
  • 没有键值相等的节点.

3）二叉搜寻树存在的局限

二叉树在查找数据时，工夫复杂度最好状况是O(logn) ，最坏状况下工夫复杂度O(n)，如a图所示，二叉树进化成一个链表了，恰好抉择了最小或者最大的节点做root，节点排在了一条直线上。

因而,在二叉查找树的根底上,又呈现了AVL树,红黑树,它们两个都是基于二叉查找树,只是在二叉查找树的根底上又对其做了限度.

  1. B树

1）概念

B树又名均衡多路查找树（查找门路不只两个），不同于常见的二叉树，它是一种多叉树，咱们常见的应用场景个别是在数据库索引技术里，大量使用者B树和B+树的数据结构。

有些教材中，也把B树称为B-树, -只是一个符号，无需太在意命名模式。

B树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据，有可能没有方法一次将须要的所有数据退出到内存中，所以只能逐个加载磁盘页，每个磁盘页就对应一个节点，而对于B树来说，B树很好的将树的高度升高了，这样就会缩小IO查问次数，尽管一次加载到内存的数据变多了，但速度相对快于AVL或是红黑树的。

2）特点

1）定义任意非叶子结点最多只有M个儿子；且M>2
2）所有节点关键字是按递增秩序排列，并遵循左小右大准则
3）位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
4）其它节点至多有M/2个子节点 [M/2,M-1]
5）所有叶子节点都在同一层

3）B树查问流程

这里应用字母来示意：

如上图我要从上图中找到E字母，查找流程如下：

（1）获取根节点的关键字进行比拟，以后根节点关键字为M，E<M（26个字母程序），所以往找到指向右边的子节点（二分法规定，左小右大，右边放小于以后节点值的子节点、左边放大于以后节点值的子节点）；

（2）拿到关键字D和G，D<E<G 所以间接找到D和G两头的节点；

（3）拿到E和F，因为E=E 所以间接返回关键字和指针信息（如果树结构外面没有蕴含所要查找的节点则返回null）；

搜寻B树时，很显著，拜访节点（即读取磁盘）的次数与树的高度呈反比，而B树与红黑树和一般的二叉查找树相比，尽管高度都是对数数量级，然而显然B树中log函数的底能够比2更大，因而，和二叉树相比，极大地缩小了磁盘读取的次数。

3.B+树

1）概念

B+树时B树的一种降级版本，B+树查找的效率要比B树更高、更稳固。

B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保留数据.),非叶子节点只保留索引,不保留理论的数据,数据都保留在叶子节点中.

这不就是文件系统文件的查找吗?咱们就举个文件查找的例子:有3个文件夹,a,b,c, a蕴含b,b蕴含c,一个文件yang.c, a,b,c就是索引(存储在非叶子节点), a,b,c只是要找到的yang.c的key,而理论的数据yang.c存储在叶子节点上.
所有的非叶子节点都能够看成索引局部

2）特点

B+树和B树相似，但多了几条规定

  • 非叶子结点的子树指针个数与关键字（节点中的元素个数）个数雷同
  • 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）
  • 所有叶子结点有一个链指针
  • 所有关键字都在叶子结点呈现
  • 只有叶子节点有Data域

3）B+树与B树比照

1、B+树的层级更少：相较于B树，B+每个非叶子节点存储的要害字数更多，树的层级更少所以查问数据更快；

2、B+树查问速度更稳固：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都雷同所以查问速度要比B树更稳固;

3、B+树人造具备排序功能：B+树所有的叶子节点数据形成了一个有序链表，在查问大小区间的数据时候更不便，数据紧密性很高，缓存的命中率也会比B树高。

4、B+树全节点遍历更快：B+树遍历整棵树只须要遍历所有的叶子节点即可，，而不须要像B树一样须要对每一层进行遍历，这有利于数据库做全表扫描。

B树绝对于B+树的长处是，如果常常拜访的数据离根节点很近，而B树的非叶子节点自身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B+树绝对于B树的最次要的长处：

  1. B+树只有叶子节点存放数据，而其余节点只寄存索引，而B树每个节点都有Data域。所以雷同大小的节点B+树蕴含的索引比B树的索引更多（因为B树每个节点还有Data域）
  2. B+树的叶子节点是通过链表连贯的，所以找到上限后能很快进行区间查问，比B树中序遍历快
  1. AVL树（均衡二叉树）

1）概念

AVL、红黑树是对二叉搜寻树的改良版本。

均衡因子：节点的左右子树深度之差。在一棵均衡二叉树中，节点的均衡因子只能取 0 、1 或者 -1 ，别离对应着左右子树等高，左子树比拟高，右子树比拟高。

AVL树是带有平衡条件的二叉查找树，个别是用均衡因子差值判断是否均衡并通过旋转来实现均衡，左右子树树高不超过1，和红黑树相比，它是严格的均衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。

不论咱们是执行插入还是删除操作，只有不满足下面的条件，就要通过旋转来保持平衡，而旋转是十分耗时的，由此咱们能够晓得AVL树适宜用于插入删除次数比拟少，但查找多的状况。

由上图所知：任意节点的左右子树的均衡因子差值都不会大于1

2）AVL保持平衡的四种操作

增删改查操作和二分搜寻树相似，然而要多思考的就是对节点的均衡思考，如果一串数字的插入程序为3，4，5。那么这棵树结构就会进化为一个链表。而这时候AVL就会对这个树进行旋转操作来达到均衡，所以，咱们就晓得旋转的操作会在减少，删除，批改这三个中央进行旋转。旋转操作分为上面四种状况

1. LL右单旋转

如图，8的左子树曾经进化为链表，并且5，8这两个节点不再均衡，这时咱们先找到深度最深的不均衡节点5，对节点5进行LL旋转操作，在如图的这种状况下，失去右图的构造

2. RR左单旋转

如图，当插入程序为当插入程序为8，3，10，13，15的时候，树的构造变成右边的样子，这时10节点和8节点曾经不均衡，为了放弃AVL的均衡，咱们要对10节点进行RR旋转，如右图所示

3. LR先左后右

如图。5，8节点曾经不均衡，这时要对5节点做均衡解决，首先将5进行RR左旋转，7的左节点也变为5的右节点。

这时7，8还是不均衡的，对8进行右旋转，8的右节点也变为8的左节点，如图。

4. RL先右后左

如左图，8，13节点不均衡，对13节点进行LL右旋转，失去右图

这时8，10是不均衡的，对8节点进行RR左旋转，失去右图。

以上就是保持平衡的形式。

3）AVL存在的局限性

因为保护这种高度均衡所付出的代价比从中取得的效率收益还大,故而理论的利用不多，

更多的中央是用谋求部分而不是十分严格整体均衡的红黑树.当然,如果利用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树.

  1. 红黑树

1）概念

一种二叉查找树，但在每个节点减少一个存储位示意节点的色彩，能够是red或black（非红即黑）。通过对任何一条从根到叶子的门路上各个节点着色的形式的限度，红黑树确保没有一条门路会比其它门路长出两倍。它是一种弱均衡二叉树(因为是弱均衡，能够推出，雷同的节点状况下，AVL树的高度低于红黑树)，绝对于要求严格的AVL树来说，它的旋转次数少，所以对于搜寻、插入、删除操作较多的状况下，咱们就用红黑树。

2）特色

1、每个节点非红即黑；

2、根节点是黑的；

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

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

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

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

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

3）红黑树的自均衡操作

但插入、或者删除红黑树的数值时，为了从新合乎红黑树的规定，须要对红黑树进行旋转、变色操作。

当在对红黑树进行插入和删除等操作时，对树做了批改可能会毁坏红黑树的性质。为了持续放弃红黑树的性质，能够通过对结点进行从新着色，以及对树进行相干的旋转操作，即通过批改树中某些结点的色彩及指针构造，来达到对红黑树进行插入或删除结点等操作后持续放弃它的性质或均衡的目标。

树的旋转分为左旋和右旋，上面借助图来介绍一下左旋和右旋这两种操作。

  • 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点放弃不变。

 应用动图更好了解：【由动图可知，红黑树并不是简略的旋转，须要随同着子树的转换】

  • 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点放弃不变。

应用动图更好了解：

 

咱们先疏忽色彩，能够看到旋转操作不会影响旋转结点的父结点，父结点以上的构造还是放弃不变的。
左旋只影响旋转结点和其右子树的构造，把右子树的结点往左子树挪了。
右旋只影响旋转结点和其左子树的构造，把左子树的结点往右子树挪了。

所以旋转操作是部分的。另外能够看出旋转能放弃红黑树均衡的一些打量了：当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。

  • 变色：结点的色彩由红变黑或由黑变红。

Java _TreeMap_实现了_SortedMap_接口，也就是说会依照key的大小程序对_Map_中的元素进行排序，key大小的评判能够通过其自身的天然程序（natural ordering），也能够通过结构时传入的比拟器（Comparator）。_TreeMap_底层通过红黑树（Red-Black tree）实现

看一下红黑树插入一个数值，红黑树自均衡的一个过程：

6. 二叉搜寻树、B树、B+树、AVL树、红黑树的常见面试题

1）为什么设计红黑树

红黑树通过它规定的设定，确保了插入和删除的最坏的工夫复杂度是O(log N) 。

红黑树解决了AVL均衡二叉树的保护起来比拟麻烦的问题，红黑树，读取略逊于AVL，保护强于AVL，每次插入和删除的均匀旋转次数应该是远小于均衡树。

因而：

绝对于要求严格的AVL树来说，红黑树的旋转次数少，所以对于插入、删除操作较多的状况下，咱们就用红黑树。然而，只是对查找要求较高,那么AVL还是较优于红黑树.

2）B树的作用

B树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据，有可能没有方法一次将须要的所有数据退出到内存中，所以只能逐个加载磁盘页，每个磁盘页就对应一个节点，而对于B树来说，B树很好的将树的高度升高了，这样就会缩小IO查问次数，尽管一次加载到内存的数据变多了，但速度相对快于AVL或是红黑树的。

3）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树。

4）B树和红黑树的区别

最大的区别就是树的深度较高，在磁盘I/O方面的体现不如B树。

要获取磁盘上数据，必须先通过磁盘移动臂挪动到数据所在的柱面，而后找到指定盘面，接着旋转盘面找到数据所在的磁道，最初对数据进行读写。磁盘IO代价次要破费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。依据磁盘查找存取的次数往往由树的高度所决定。

所以，在大规模数据存储的时候，红黑树往往呈现因为树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。在这方面，B树体现绝对优异，B树能够有多个子女，从几十到上千，能够升高树的高度。

5）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还是优于红黑的。

6）数据库为什么应用B树，而不应用AVL或者红黑树

咱们假如B+树一个节点能够有100个关键字，那么3层的B树能够包容大略1000000多个关键字（100+101100+101101*100）。而红黑树要存储这么多至多要20层。所以应用B树绝对于红黑树和AVL能够缩小IO操作

7）mysql的Innodb引擎为什么采纳的是B+树的索引形式

B+树只有叶子节点存放数据，而其余节点只寄存索引，而B树每个节点都有Data域。所以雷同大小的节点B+树蕴含的索引比B树的索引更多（因为B树每个节点还有Data域）

还有就是B+树的叶子节点是通过链表连贯的，所以找到上限后能很快进行区间查问，比B树中序遍历快

8）红黑树 和 b+树的用处有什么区别？

  1. 红黑树多用在外部排序，即全放在内存中的，STL的map和set的外部实现就是红黑树。
  2. B+树多用于外存上时，B+也被成为一个磁盘敌对的数据结构。

9）为什么B+树比B树更为敌对

  • 磁盘读写代价更低
    树的非叶子结点外面没有数据，这样索引比拟小，能够放在一个blcok（或者尽可能少的blcok）外面。防止了树形构造一直的向下查找，而后磁盘不停的寻道，读数据。这样的设计，能够升高io的次数。
  • 查问效率更加稳固
    非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当。
  • 遍历所有的数据更不便
    B+树只有遍历叶子节点就能够实现整棵树的遍历，而其余的树形构造 要中序遍历才能够拜访所有的数据。

参考：

https://www.cnblogs.com/carpenterlee/p/5503882.html

https://www.jianshu.com/p/86a1fd2d7406

https://juejin.im/post/6844903859974848520#heading-16

https://blog.csdn.net/whoamiyang/article/details/51926985

https://marian5211.github.io/2018/03/09/B%E6%A0%91%E3%80%81B-%E6%A0%91%E3%80%81AVL%E6%A0%91%E3%80%81Trie%E6%A0%91%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8%E5%9C%BA%E6%99%AF/

最初的最初，欢送关注公众号。。。。。

------------------------  end -------------------------------------