共计 3154 个字符，预计需要花费 8 分钟才能阅读完成。
哈希表 (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 + 树作为索引的组织形式。
各种数据结构的比照
在这里间接以最简单明了的形式突出各个数据结构的优缺点：