数据库索引的作用是做数据的快速检索，而快速检索实现的本质是数据结构。像二叉查询树、红黑树、AVL 树（平衡二叉树）、B 树、B + 树、哈希等数据结构都可以实现索引，但其中 B + 树效率最高。
MySQL 数据库索引使用的是 B + 树。
二叉查询树：二叉树中，左子树比根节点小，右子树比根节点大，每次寻找目标值都是二分查找的方式，所以二叉树的时间复杂度为 O（logn）。但当大量数据发生倾斜的时候，极端情况下，二叉树会形成链表一样的线性结构，其时间复杂度为 O（n），降低了查询效率；而且每次从磁盘读取一个节点到内存就进行一次 IO，当二叉树深度越深，IO 次数就越多，所以综上两点，二叉树不利于做索引。
红黑树：红黑树是二叉树的进阶版，当二叉树处于不平衡的状态时，红黑树就会自动左旋右旋节点使二叉树保持基本的平衡状态，也保证了查询效率不会明显地降低。但当大量数据发生倾斜时，红黑树并没有从根本上解决数据倾斜的问题，只是不会像二叉树一样变成线性结构那么夸张。
比如数据库主键递增，主键一般都有上百上千万个，红黑树存在这种倾斜问题，那对查询性能而言也是巨大的消耗，数据库不可能忍受这种毫无意义的等待。
AVL 树：AVL 树是个绝对的平衡二叉树，所以 AVL 树不存在二叉树、红黑树的数据倾斜问题。大量的顺序插入不会导致查询性能的降低，这从根本上解决了二叉树、红黑树的数据倾斜问题。但数据库查询数据的瓶颈在于磁盘 IO， AVL 树是二叉树的一种，每一个树节点只存储了一个数据，随着插入的数据越多，树的深度也越深，意味着 IO 次数就越多，所以也影响读取的效率。
这就引入了 B 树、B + 树，一个树节点上尽可能多地存储数据，这样一次磁盘 IO 就可以加载多个数据到内存中，提高查询效率。
B 树：B 树又叫平衡多路查找树，一棵 m 阶的 B 树有如下性质:
（1）树中每个结点至多有 m 个孩子节点（即至多有 m-1 个关键字）
（2）每个结点中包括 “n：记录结点中关键字的个数”、“p0....pn：孩子节点” 以及 “k1...kn：关键字”。
（3）除根节点外，其他节点至少有 ceil（m/2）个孩子结点。（ceil 函数：向上取整）
（4）若根节点不是叶子结点，则根节点至少有两个孩子结点。
（5）所有叶子结点都要在同一层上。
B 树要求每个节点不仅包含数据的 key 值，还有 data 值。而每页的存储空间有限，如果 data 比较大的话，会导致每个节点的 key 存储的较少，当数据量大的时候，同样会导致 B 树很深，从而增加磁盘的 IO 次数，进而影响查询效率。
B + 树是 B 树的进阶版，B + 树与 B 树的区别：
（1）B 树中每个根结点既有 key 又有 data 数据，而 B + 树中根节点只有 key 没有 data 数据。这样可以存储较多的 key，降低 B + 树的高度，从而减少 IO 的次数。
（2）B 树中叶子结点之间没有关联，而 B + 树中叶子结点的关键字从小到大排序，叶子结点相互之间有一个引用链路将叶子结点连接起来，像链表一样。
（3）B 树查找数据可能不用找到叶子结点就找到数据，而 B + 树把所有的数据都放在叶子结点上，所以每次查找的次数都相同，B + 树查询速度比 B 树更稳定。
（4）遍历全部结点时，B 树要对每一层都进行遍历，而 B + 树只需要遍历所有的叶子结点即可，这有利于数据库做全表扫描。
参考：MySQL 索引底层原理
