为什么数据库索引使用B+树实现
数据库索引通常使用B树及其变种B+树。数据库索引是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。
为了弄清楚数据库索引为B+树的原因，我们先来介绍B+树几个“近亲”。
1.二叉树
二叉树是每个结点只能有两个子树的树结构。
特点：
* 每个结点最多有两棵子树；
* 二叉树有左右子树之分。
二叉树逻辑上分为5种形态：空树、一个结点、只有左子树、只有右子树、完全二叉树。二叉树是通过以上几个形态组合或嵌套形成的。
性质：
* 若规定根结点的层数为1，则一棵非空二叉树的第i层最多有2(i-1)个结点；
* 若规定只有根结点的二叉树深度为1，则深度为K的二叉树的最大节点数为(2^K)-1；
* 任何一棵二叉树，度为0的结点数=度为2的结点数+1。
* 结点个数为n的完全二叉树，深度为log2(n+1)。
二叉树的存储结构：
顺序存储、链式存储。
顺序存储优点是存取完全二叉树，节省空间，缺点是类似于单支树的情况不方便存储。一般采用链式进行存储二叉树。
2.二叉搜索树
二叉搜索树或者是一棵空树，或者是具有以下性质的二叉树：
* 若它的左子树不为空，则左子树上所有结点的值都小于根节点；
* 若它的右子树不为空，则右子树上的所有结点的值都大于根节点；
* 它的左右子树也分别为二叉搜索树。
二叉搜索树如果退化为类似于单支树的话，查找效率大大降低了，几乎为线性结构，和顺序查找差不多。如果想更大性能的构造一个二叉查找树，这个二叉树需要是平衡的，从而引出了一个新的定义—AVL树。
二叉搜索树
3.AVL树
AVL树是一棵平衡树，要求左右子树的高度差的绝对值不超过1.
一棵AVL树可以为空树，或者具有以下性质的树：
* 左右子树都为AVL树；
* 左右子树的高度之差的绝对值不超过1.
AVL树是严格的平衡二叉树，平衡条件必须满足，不管我们是执行插入还是删除操作，只要不满足左右子树高度差不超过1，都要通过旋转来保持平衡，而旋转是非常耗时间的，因此，我们可以了解到AVL树适合用于插入删除较少的，但查找多的情况。
对于维护这种高度平衡所付出代价比从中获得效率收益还大，故AVL树在实际应用中不多见，更多的地方是用追求局部而不是非常严格整齐平衡的红黑树。
AVL树
应用：
Windows NT内核中广泛存在。
4.红黑树
红黑树是一种二叉查找树，但在每个结点增加一个存储位表示结点的颜色。它是一种弱平衡二叉树，旋转次数变少，对于搜索、插入、删除等操作多的情况下，我们使用红黑树。
性质：
* 每个结点非红即黑；
* 根结点为黑；
* 每个叶结点都是黑的（即树尾端的NULL指针或NULL结点）；
* 如果一个结点是红的，那么它的子节点都为黑；
* 对于任意结点来说，其到叶子结点NULL指针中每条路径都包含相同数目的黑结点。
应用：
- STL的map和set底层都是红黑树；
- Linux下的进程调度采用红黑树管理进程控制块，进程的虚拟内存区域都存储在一棵红黑树上，每个虚拟地址区域都对应红黑树的一个结点，左指针指向相邻的地址存储虚拟区域，右指针指向高地址的虚拟地址空间；
- IO多路复用的epoll实现采用红黑树组织管理文件描述符（结点是一个结构体，包含文件描述符、事件），以支持快速的增删改查；
- Nginx中用红黑树管理timer，原因是红黑树是有序的，可以很快的得到距离当前最小的定时器；
- Java中TreeMap的实现。
5.B/B-树
B树和B-树是一个概念，B树是一个结点可以拥有多于2个子节点的二叉查找树。与平衡二叉树不同，B树的最大优点就是优化了大块数据的读写操作，B树减少定位记录时所经历的中间过程，从而加快存取速度，普遍用于数据库和文件系统。
B树允许每个结点有M-1个子节点。
性质：
* 根结点至少有两个子节点；
* 每个结点有M-1个key，并且按照升序排列；
* 位于M-1和M的子结点的值位于M-1和M的key对应的值之间（开区间，不允许关键字重复）；
* 其他结点至少有M/2个子节点。
介绍到这里，我们来谈一谈MySQL数据库索引为什么用B+树？
我们在MySQL中的数据一般存放在磁盘中，读取数据一定会访问到磁盘。
磁盘运作原理：磁盘有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们常说的多少转，磁臂移动则是进行数据读写。那么存在一个定位到磁盘中块的过程，定位是花费时间较大的一部分。当大规模数据存储到磁盘中时，定位是一个花费时间比较多的过程。所以，B树就可以对其优化，提高磁盘读取定位的效率。
与红黑树比较，一棵B/B+树的高度比较低，B/B+树的操作由磁盘读取时间和CPU计算时间这两部分组成的，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘的I/O所花的时间越少。
6.B+树
B+树是对B树的一种变种，只有叶子结点保存数据，非叶子结点只保存索引，不保存实际的数据。
性质：
* 非叶子结点的子树指针域关键字的个数相同；
* 非叶子结点的子树指针p[i]，指向关键字属于[k[i], k[i+1]]的子树（闭区间，允许关键字重复）；
* 为所有的叶子结点增加一个链指针；
* 所有关键字都在叶子结点出现；
* 非叶子结点相当于叶子结点的索引，叶子结点相当于是存储数据的数据层；
* 更适于文件系统。
为什么B+树比B树更适合做数据库索引？
- B+树的磁盘读写代价更低。由于B+树内部的结点并没有指向关键字的指针，所以其内部结点相对B树更小，如果把同一内部结点的关键字存放在同一块磁盘中，那么盘块所能容纳的关键字数量也就较多，一次性读入内存需要查找的关键字也越多，相对IO读写次数也就越低。
- B+树的查询效率更加稳定。由于非叶子结点并不是指向文件内容的结点，而只是叶子结点中关键字的索引，所以任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，导致每一个数据的查询效率一样。
- B+树在查询时，只需要扫一遍叶子结点就可以了，因为分支结点都为索引，没有存文件内容。而B树分支结点中还存在数据，我们需要找到具体的数据，需要进行一次中序遍历按序扫描，所以B+树更适合在区间查询，因此，B+树更适合用于数据库索引。