最近重新学习MySQL，发现自己一直知道MySQL索引用到了B+树，引发思考，为什么一定要是B+树，其他树或者其他数据结构不可以吗？下文揭晓。
算法图解网站，可以看到树是怎么生成的

1. 二叉查找树 (Binary Search Tree)

• 既然都是树，就先从二叉查找树开始吧。

BST的性质

• 二叉查找树也称为有序二叉查找树，二叉查找树具有以下性质：

1. 任意节点左子树不为空，则左子树的值小于根节点的值
2. 任意节点右子树不为空，则右子树的值大于根节点的值
3. 任意节点的左右子树也分别是二叉查找树

4. 没有键值相等的节点

   
   Binary Search Tree

• 上图就为一个简单的二叉查找树，二叉查找树的中序遍历是有序的，从小到大输出为：1， 3， 5， 8，9， 13
• 如果查找的键值为3，在二叉查找树中，先比较根节点大小5>3, 找其左子树，找到1，再比较1<3，找其右子树，找到3。二叉查找树找了2次，如果按照顺序查找也是2次。
• 我们依次算下平均查找次数，二叉查找树中查找次数为(1+2+2+3+3+3）/ 6 = 2.3次；如果顺序查找，查找次数为(1+2+3+4+5+6) / 6 = 3.3 次。可以看到二叉查找树的查找速度比顺序查找更快。

BST的局限性及应用

• 一个二叉查找树是由n个节点随机构成的，在某些情况中，二叉查找树会退化成一个有n个节点的线性链。如下图

  
  
• 如上图，如果我们的根节点选择是最大或者最小的数，那么二叉查找树就会退化成一个链，变成顺序查找。
• 退化了的二叉查找树查询效率非常低，于是我们就想怎么才能最大性能的构造出一个二叉查找树，使得这个二叉树是平衡的（高度相差不大），这样就引出了AVL树（二叉平衡树）

BST 的操作代价分析

(1) 查找代价：

• 任何一个数据的查找过程都需要从根结点出发，沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。
• 当树中每个结点左右子树高度大致相同时，树高为logN。则平均查找长度与logN成正比，查找的平均时间复杂度在O(logN)数量级上。

• 当先后插入的关键字有序时，BST退化成单支树结构。此时树高n。平均查找长度为(n+1)/2，查找的平均时间复杂度在O(N)数量级上。

  
  

(2) 插入代价：

新结点插入到树的叶子上，完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。

(3) 删除代价：

• 当删除一个结点P，首先需要定位到这个结点P，这个过程需要一个查找的代价。然后稍微改变一下树的形态。
• 如果被删除结点的左、右子树只有一个存在，则改变形态的代价仅为O(1)。
• 如果被删除结点的左、右子树均存在，只需要将当P的左孩子的右孩子的右孩子的…的右叶子结点与P互换，在改变一些左右子树即可。
• 因此删除操作的时间复杂度最大不会超过O(logN)。
  删除节点左右子树都在

时间复杂度分析

• 当树中每个结点左右子树高度大致相同时，树高为logN。则平均查找长度与logN成正比，查找的平均时间复杂度是O(logN)
• 当先后插入的关键字有序时，BST退化成单支树结构。此时树高n。因此最差时间复杂度是O(N)。
• 插入删除操作算法简单，时间复杂度与查找差不多。

2. AVL树（平衡二叉查找树）

• 我们不能忍受二叉查找树在最差的情况下（链式）的时间复杂度和顺序查找的时间复杂度一致。因为当数据够大的时候，左右子树可能会有很大的高度差，为了防止这种情况，AVL树横空出世！
• AVL树本质上就是带有平衡条件的二叉查找树
• AVL树在左子树与右子树的高度差大于1的时候进行调整。

二叉查找树 二叉平衡树

• 上图是一个二叉查找树通过左旋变成AVL树的过程，通过上面的gif图可以看出，任意节点的左右子树的平衡因子的差值都不会大于1。

AVL 的操作代价分析

• 我们还是使用[1， 3， 5， 8，9， 13] 这6个节点
  [站外图片上传中...(image-6e0bd7-1597541595431)]

(1) 查找代价：

AVL是严格平衡的BST（平衡因子不超过1）。那么查找过程与BST一样，只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好，最坏情况都是O(logN)数量级的。

AVL查找节点

(2) 插入代价：

• AVL必须要保证严格平衡(|bf|<=1)，那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。
• 事实上，AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。
• 因此，总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。
  [站外图片上传中...(image-fc03e8-1597541595431)]

(3) 删除代价：

• AVL删除结点的算法可以参见BST的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。
• 因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。
• 因此，删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)
  [站外图片上传中...(image-d72429-1597541595431)]

时间复杂度分析

• 查找的时间复杂度维持在O(logN)，不会出现最差情况
• AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。
• AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。

3. 红黑树

• 二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN) 的查找时间复杂度。但是这样做是否值得呢？
• 能不能找一种折中策略，即不牺牲太大的建立查找结构的代价，也能保证稳定高效的查找效率呢？ 答案就是：红黑树。

红黑树简介

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

红黑树性质

1. 每个节点非红即黑
2. 根节点必须是黑的
3. 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
4. 如果一个节点是红的,那么它的两儿子都是黑的；
5. 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
6. 每条路径都包含相同的黑节点；

• 性质3中指定红黑树的每个叶子节点都是空节点，而且叶子节点都是黑色。但是Java实现的红黑树将使用null来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，可以看到叶子节点有红色的

• 性质4的意思是从根到节点的路径上不会有两个连续的红色节点，但是黑色节点是可以连续的。因此如果给定黑色节点的个数为N，最短路径的情况是连续的N个黑色，树的高度为N-1；最长路径的情况为节点红黑相同，树的高度为2（N-1）

• 性质5是成为红黑树的最主要的条件，后序的插入、删除操作都是为了遵守这个规定。

红黑树性质

• 我们还是使用[1， 3， 5， 8，9， 13] 这6个节点构造红黑树

  
  构造红黑树

(1) 查找代价：

• 由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。

• 其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。

  
  RBT查找节点

(2) 插入代价：

• RBT插入结点时，需要旋转操作和变色操作。* 但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。

• 虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。

  
  RBT插入节点

(3) 删除代价：

RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。

RBT删除节点

RBT 效率总结 :

• 查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。
• 插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。
• 虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。

红黑树的应用

1. 广泛用于C++的STL中，Map和Set都是用红黑树实现的；
2. 著名的Linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
3. IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查；
4. Nginx中用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
5. Java中TreeMap的实现；

红黑树为什么是在内存中使用的数据结构？

• 为什么数据库中不使用红黑树进行查找呢？
• 将大量数据全部放入内存组织成RBT结构显然是不实际的。实际上，像OS中的文件目录存储，数据库中的文件索引结构的存储…. 都不可能在内存中建立查找结构。数据必须在磁盘中建立好这个结构。
• 这就涉及到磁盘的存储原理了，操作系统读写磁盘的基本单位是扇区，而文件系统的基本单位是簇（Cluster）（每个簇或者块可以包括2、4、8、16、32、64…2的n次方个扇区。）。

• 意思就是，磁盘读写有一个最少内容的限制，即使我们只需要这个簇上的一个字节，我们也必须把整个簇的内容都读完。

  
  
• 那么现在就有一个悲催的事情了，
• 如果一个父节点只有2个子结点，并不能填满一个簇上的所有内容，那多余的地方就浪费了，考虑到磁盘的存储原理，B/B+树应运而生了。
• 由于B/B+树分支比二叉树多，所以相同数量的内容，B+树的深度更浅。B+树的深度就代表了磁盘的 I/O 次数。
• 数据库设计的时候B+树有多少个分支都是按照磁盘上一个簇最多能放多少节点设计的，
• 因此一般来说，涉及到磁盘上查询的数据结构，都是使用B/B+树
  [图片上传失败...(image-573a3a-1597541595431)]

4. B树

• 先来看看B树，B树也称B-树，是一棵多路平衡查找树，我们描述一棵B树时需要指定他的阶数。阶数表示一个结点最多有多少个孩子结点。一般我们用字母m表示阶数，当m取2时，就是我们常见的二叉树。

B树的性质

• 一棵m阶的二叉树定义如下：

1. 每个节点最多有m-1个关键字
2. 根节点最少可以只有1个关键字
3. 非根节点至少有math.ceil(m/2) - 1 个关键字 (math.ceil表示向上取整)
4. 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5. 所有叶子结点都位于同一层（或者说根节点到每个叶子节点的长度都相同）

4阶B树

• 上图是一颗阶数为4的B树，实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。
• B树中的每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。
• 我们将一个key和其对应的data称为一个记录。
• 但为了方便描述，除非特别说明，后续文中就用key来代替（key, value）键值对这个整体。
• 在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速度，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。

B树的查找操作

• B-Tree作为一个平衡多路查找树(m-叉)。B树的查找分成两种：

1. 一种是从一个结点查找另一结点的地址的时候，需要定位磁盘地址(查找地址)，查找代价极高。
2. 另一种是将结点中的有序关键字序列放入内存，进行优化查找(可以用折半)，相比查找代价极低。而B树的高度很小，因此在这一背景下，B树比任何二叉结构查找树的效率都要高很多。而且B+树作为B树的变种，其查找效率更高。

B树的插入操作

• 插入操作是指插入一条记录，即（key, value）的键值对。

• 如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

• B树的插入步骤：

1. 根据要插入的key的值，找到叶子结点并插入。
2. 判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
3. 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。

下面以5阶B树为例，介绍B树的插入操作，在5阶B树中，结点最多有4个key,最少有2个key

---

a）在空树中插入39

此时根结点就一个key，此时根结点也是叶子结点

---

b）继续插入22，97和41

根结点此时有4个key

---

c）继续插入53

• 插入后超过了最大允许的关键字个数4，所以以key值为41为中心进行分裂，
• 结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。
• 当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

---

d）依次插入13，21，40，同样会造成分裂，结果如下图所示。

---

e）依次插入30，27, 33 ；36，35，34 ；24，29，结果如下图所示。

---

f）插入key值为26的记录，插入后的结果如下图所示。

当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示。

进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示。

分裂后当前结点指向新的根，此时无需调整。

---

g）最后再依次插入key为17,28,29,31,32的记录，结果如下图所示。

---

• 在实现B树的代码中，为了使代码编写更加容易，我们可以将结点中存储记录的数组长度定义为m而非m-1，这样方便底层的结点由于分裂向上层插入一个记录时，上层有多余的位置存储这个记录。

• 同时，每个结点还可以存储它的父结点的引用，这样就不必编写递归程序。

• 一般来说，对于确定的m和确定类型的记录，结点大小是固定的，无论它实际存储了多少个记录。

• 但是分配固定结点大小的方法会存在浪费的情况，比如key为28,29所在的结点，还有2个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个结点的前序key是27,后继key是30,所有整数值都用完了。

• 所以如果记录先按key的大小排好序，再插入到B树中，结点的使用率就会很低，最差情况下使用率仅为50%。

B树的删除操作

• 删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1. 如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2. 该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。

3. 如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

4. 否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

下面以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key,最少有2个key

---

a）原始状态

---

b）在上面的B树中删除21，删除后结点中的关键字个数仍然大于等2，所以删除结束。

---

c）在上述情况下接着删除27。从上图可知27位于非叶子结点中，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下图所示。

删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示。

---

d）在上述情况下接着删除32，结果如下图。

当删除后，当前结点中只有1个key，而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示。

当前结点key的个数满足条件，故删除结束。

---

e）上述情况下，我们接着删除key为40的记录，删除后结果如下图所示。

同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

同理，对于当前结点而言只能继续合并了，最后结果如下所示。

合并后结点当前结点满足条件，删除结束。

• 终于讲完了B树的操作，也知道为什么数据库索引使用B树而不用红黑树了

• 但是！！！我们还想更优化一点

• B树的每个节点都有data域（指针），这个操作就会增大节点的大小，说白了也就是会增加磁盘I/O次数（磁盘I/O一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，IO多耗时就长啊朋友！）

• 那我们是不是可以出了叶子节点外，其他节点不存储数据，节点小，磁盘IO次数就少。

• 我们还可以将所有在叶子节点的Data域用指针连接成链，这样遍历叶子节点就能获得全部的数据，这样也能进行顺序查找（支持区间访问），遍历效率也会提高。

• 在数据库中基于范围的查询是非常频繁的，如果使用B树，效率会非常低。

5. B+树

• B+树定义：关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。下面是一颗阶数为4的B+树。
  

除此之外B+树还有以下的要求。

1. B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

2. B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

3. m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

4. 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

5）每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

B+树的插入操作

1. 若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。
2. 针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
3. 针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

下面是一颗5阶B树的插入过程，5阶B数的结点最少2个key，最多4个key。

---

a）空树中插入5

---

b）依次插入8，10，15

---

c）插入16

插入16后超过了关键字的个数限制，所以要进行分裂。在叶子结点分裂时，分裂出来的左结点2个记录，右边3个记录，中间key成为索引结点中的key，分裂后当前结点指向了父结点（根结点）。结果如下图所示。

当然我们还有另一种分裂方式，给左结点3个记录，右结点2个记录，此时索引结点中的key就变为15。

---

d）插入17

---

e）插入18，插入后如下图所示

当前结点的关键字个数大于5，进行分裂。分裂成两个结点，左结点2个记录，右结点3个记录，关键字16进位到父结点（索引类型）中，将当前结点的指针指向父结点。

当前结点的关键字个数满足条件，插入结束。

---

f）插入若干数据后

---

g）在上图中插入7，结果如下图所示

当前结点的关键字个数超过4，需要分裂。左结点2个记录，右结点3个记录。分裂后关键字7进入到父结点中，将当前结点的指针指向父结点，结果如下图所示。

当前结点的关键字个数超过4，需要继续分裂。左结点2个关键字，右结点2个关键字，关键字16进入到父结点中，将当前结点指向父结点，结果如下图所示。

当前结点的关键字个数满足条件，插入结束。

B+树的删除操作

如果叶子结点中没有相应的key，则删除失败。否则执行下面的步骤

1. 删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束,否则执行第2步。

2. 若兄弟结点key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行第3步。

3. 若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第4步（第4步以后的操作和B树就完全一样了，主要是为了更新索引结点）。

4. 若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1，则删除操作结束。否则执行第5步

5. 若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步

6. 当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。

注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。

下面是一颗5阶B树的删除过程，5阶B数的结点最少2个key，最多4个key。

---

a）初始状态

---

b）删除22,删除后结果如下图

删除后叶子结点中key的个数大于等于2，删除结束

---

c）删除15，删除后的结果如下图所示

删除后当前结点只有一个key,不满足条件，而兄弟结点有三个key，可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9，删除结束。

---

d）删除7，删除后的结果如下图所示

当前结点关键字个数小于2，（左）兄弟结点中的也没有富余的关键字（当前结点还有个右兄弟，不过选择任意一个进行分析就可以了，这里我们选择了左边的），所以当前结点和兄弟结点合并，并删除父结点中的key，当前结点指向父结点。

此时当前结点的关键字个数小于2，兄弟结点的关键字也没有富余，所以父结点中的关键字下移，和两个孩子结点合并，结果如下图所示。

图文引用

B+树性能分析

• B+树中一次检索最多需要h-1次IO，（根节点常驻内存），渐进复杂度为O(h) = O(logmN)。
• 实际应用中，m是非常大的数字，通常超过100，因此h非常小（通常不超过3）
• 意思就是，用B+树作为索引结构效率是非常高的。红黑树的结构，h明显非常深，查询效率会低很多

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

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

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

PS：我在知乎上看到有人是这样说的,我感觉说的也挺有道理的：

他们认为数据库索引采用B+树的主要原因是：B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。