哈希表(Hash)
哈希表查问数据的工夫复杂度为O(1)，是一种高效的数据结构。面试中常问的HashMap就是基于哈希表的思维，对HashMap不太深刻的同学，能够参考我的另外一篇文章HashMap夺命连环问
例如将索引列作为key，对应行的物理地址作为value，十分实用于解决等值查问。
select * from user where id=1;
但哈希表不言而喻的毛病就是，哈希表不适用于范畴查找。
例如执行以下语句时，哈希表就无能为力了。
select * from user where id>1;
二叉搜寻树(Binary Search Tree)
常常刷LeetCode的同学，必定是晓得二叉搜寻树的中序遍历是一个递增序列。
一颗二叉搜寻树，每个节点最多只有2个子节点，左子节点的值小于父节点，右子节点的值大于父节点。
在java培训中二叉搜寻树中进行查问，能够利用到二分查找，因而查问的工夫复杂度为O(logN)。
例如查找元素23时，先从根节点开始，因为23>20，路由到右子节点32上。因为23<32，路由到其左子节点23上，发现相等，查问完结。
仅需比拟3次，就能够查问到想要的数据。
另外，二叉搜寻树的插入与删除操作的工夫复杂度也为O(logN)，有趣味的同学能够做做LeetCode上的这道题701. 二叉搜寻树中的插入操作
咱们大能够将索引列作为节点的值，同样每个节点还有个用于保留相应行物理地址的变量。
二叉搜寻树反对范畴查找，例如对以下的sql语句
select * from user where id>12 and id<32;
首先利用二分查找到节点12，再对此节点进行中序遍历，在遍历到节点32时进行即可。
二叉搜寻树在搜寻、插入与删除放弃较优的工夫复杂度，而且又反对范畴查找。那MySQL为啥没有应用它呢？
是因为二叉搜寻树在插入、删除的过程中并不会放弃本身的均衡！
例如我新增了3条用户数据，初始的树是这样的（节点的值为主键）：
当我再次减少3条数据后，节点被顺次加在右子树上，最终造成链表的构造。
此时，二叉搜寻树进化成了链表，工夫复杂度由O(logN)晋升到了O(N)，查问性能大大降低。
因而，咱们迫切需要一种可能在变动中放弃自均衡的二叉树。
均衡二叉搜寻树
AVL树
AVL树就是一种自均衡的二叉搜寻树，对于它的任意一个节点，其左子树高度与右子树高度差最大为1，因而就不存在二叉树进化为链表的极其状况。
下图就是一个AVL树：
在往AVL树中插入节点时，须要通过左旋右旋操作来保障树的平衡性。
AVL树在查找、插入与删除操作的工夫复杂度都为O(logN)。
AVL树谋求极致的平衡性，因而就会进行屡次的旋转。在插入与删除次数比拟多时，达成均衡的代价甚至比应用它的收益还要大。
那有没有一种可能略微升高点平衡性，却能带来较大的整体性能上晋升的均衡二叉搜寻树呢？
红黑树
红黑树也是一种均衡二叉搜寻树，相比于AVL树。红黑树仿佛对平衡性的谋求没有那么执着，红黑树只要求最长门路不能超出最短门路的两倍。
在红黑树中，节点要么是红色，要么是彩色。根节点与叶子节点（NIL）都是彩色的，任意一个门路不能间断呈现2个红色节点。从根节点登程的所有门路，彩色节点（不蕴含NIL）的数量都是雷同的。
红黑树通过左旋、右旋与变色三种操作来保障肯定的平衡性，相比于AVL树，红黑树的查问效率较低，然而删除与插入的效率大大提高，总体性能优于AVL树。
而且在理论的利用中，红黑树的利用更加宽泛。例如HashMap在链表长度大于8时则转化为红黑树，TreeMap应用红黑树来对键值进行排序，IO多路复用中epoll应用红黑树来对Socket进行治理。
那MySQL为啥没有应用红黑树来组织索引数据呢？
如果索引数据可能一次性加载到内存中，那么应用红黑树是没有问题的。
问题就在于，索引数据无奈一次性加载到内存中，因而索引数据须要分批加载。
假如要查问的数据位于叶子节点上，树高为n。第一次先把根节点加载到内存中，进行一次磁盘IO。当始终查问到叶子节点时，就须要进行n次IO。
当单表数据达到100万时，树的高度约为log1000000(以2为底)=20。一次磁盘IO均匀耗时10ms，20次就是0.2秒。如果再思考到范畴查问、不走索引的查问与多表联查，速度慢得令人发指。
因而，咱们当初的首要指标，就是升高IO次数，也就是升高树的高度。
B树
B树又称为B-树，留神不是B减树啊，“-”是一个连字符！！！
B树是一种多叉均衡搜寻树，在节点总数雷同的状况下，B树的高度显著低于二叉树。
B树有以下几个重要的个性：
每个节点可能存储多个元素，节点内元素是有序的，每一个元素也会对应一份数据行（当然也有可能是主键索引项，或者数据行的地址）。
父节点中的元素不会呈现在子节点当中
叶子节点都在同一层，且之间没有通过指针相连
一颗具备3个分叉的B树为：
能够看到，B树的高度被压缩得很厉害。
另外一个方面，B树充分利用到了程序拜访的局部性原理。也就是说，当程序拜访磁盘或内存中的一份数据时，其四周的数据将会有很大概率在接下来被应用到。
因而，B数每个节点不会只存一个元素，而是存储多份。咱们查问数据时，每进行一次IO，就会将B树的一个节点读进缓存中。这样在接下拜访其四周的数据时，无需从磁盘读取，间接从缓存读取，缓存命中率大大晋升。
兴许会有人问？如果一个节点内寄存大量元素，那么从磁盘读取的速度是否和个数相干，呈线性增长呢？
答案是不会的。第一次读取一个节点时，进行的是随机读，须要先进行磁盘寻道，是十分耗时的。之后读取其余的元素，是进行的程序读。之所以进行程序读，是因为一个节点内的元素被顺序存储在磁盘上的。程序读是十分疾速的，其效率可能千倍于随机读。
那么，在B树上读取索引项为21的流程是怎么的呢？
在节点外部，应用的是二分查找，用于找到上层指针。
看来B树能无效解决均衡二叉树io次数过多的问题，仿佛曾经能满足所有的要求了。
然而MySQL最终采纳的B+树，而不是B树。
相对来说，B树还有以下的有余：
每个节点不仅存索引项，又存具体的数据，那么每个节点可寄存的索引项就比拟少。索引项少，io次数就会变多。
B树不能做到疾速的范畴查找，须要进行屡次的查找，相似于中序遍历。
为了改良B树，起初提出了B+树。
B+树
这个时候你又能够读作B加树了…
B+树有以下的个性：
非叶子节点只寄存索引项，叶子节点既寄存索引项，也寄存具体的数据。
叶子节点会寄存以后所有的索引项，就是说，能够与父节点的索引项反复。
叶子节点通过指针相连，造成有序的双向链表构造。
一颗成熟的B+树，应该是有如下的风格：
因为B+树叶子节点才存放数据行，因而每次的查问，都须要加载到叶子节点。而B树每个节点都存放数据行，每次的查问不肯定非要到叶子节点。
所以这个时候会有人收回这样的疑难：B+树每次查问必须要深刻到叶子节点，那么它的均匀查问效率不是应该低于B树的吗？
如果在树高雷同的状况下，的确是的。可理论状况是，在索引项雷同的状况下，B+树的高度显著低于B树的，因为B+树的非叶子节点能够比B树寄存更多的元素，毕竟少了数据行嘛。所以思考到io老本加上范畴查问，B+树的整体查问效率是优于B树的，但B+树对单个数据的查问效率是低于B树的。
B+树在范畴查问上，是怎么体现出不错的性能的呢？
首先查找到范畴上限，间接应用叶子节点的指针来加载下一个数据块，防止通过父节点来直达。在遍历到范畴下限后，间接返回遍历到的所有数据即可。
B+树通过在叶子节点反复存储元素，其整体占用的空间其实是略高于B树的。但这点节约的空间却可能换来微小的性能晋升，也是蛮不错的。
鉴于B+树用于以上的长处，MySQL最终采纳了B+树作为索引的组织形式。
各种数据结构的比照
在这里间接以最简单明了的形式突出各个数据结构的优缺点：
转载请注明原文链接：关于java:探究MySQL的索引结构选型
