哈希表（Hash）哈希表查询数据的时间复杂度为O(1)，是一种高效的数据结构。面试中经常被问到的HashMap，就是基于哈希表的思想。对HashMap不是很熟悉的同学可以参考我的另一篇文章HashMap。适用于处理等价查询。从id=1的用户中选择*；但是哈希表的明显缺点是哈希表不适合范围查找。比如下面的语句执行时，哈希表就无能为力了。从id>1的用户中选择*；二叉搜索树（BinarySearchTree）经常用LeetCode的同学一定知道，二叉搜索树的中序遍历是一个递增的序列。一棵二叉搜索树，每个节点最多有2个子节点，左子节点的值小于父节点，右子节点的值大于父节点。java训练中在二叉搜索树中查询可以使用二分查找，所以查询的时间复杂度为O(logN)。比如查找元素23时，从根节点开始，因为23>20，所以路由到右子节点32。因为23<32，所以路由到它的左子节点23，发现是相等的,查询结束。只需要比对3次，就可以查询到想要的数据。另外，二叉搜索树的插入和删除操作的时间复杂度也是O(logN)。有兴趣的同学可以在LeetCode上做这道题701。对于二叉搜索树中的插入操作，我们可以使用索引列为节点的值，每个节点还有一个变量，用于存储对应行的物理地址。二叉搜索树支持范围搜索，例如对于下面的sql语句select*fromuserwhereid>12andid<32;先用二分查找找到节点12，然后对这个节点进行中序遍历，当遍历到节点32时才停止。二叉搜索树在搜索、插入和删除上保持了较好的时间复杂度，支持范围搜索。那么为什么MySQL不使用它呢？就是因为二叉搜索树在插入和删除的时候没有保持自己的平衡！比如我添加了3条用户数据，初始树是这样的（节点的值为主键）：当我再次添加3条数据时，节点依次添加到右子树中，最后形成一个链表结构。此时二叉搜索树退化为链表，时间复杂度由O(logN)增加到O(N)，查询性能大大降低。因此，我们迫切需要一种能够在变化中保持自我平衡的二叉树。平衡二叉搜索树AVL树AVL树是一种自平衡二叉搜索树。对于它的任意一个节点，左子树的高度和右子树的高度之差至多为1，所以不存在退化为链表的二叉树。极端情况。下图是一棵AVL树：向AVL树中插入节点时，需要通过左手和右手操作来保证树的平衡。AVL树在查找、插入和删除操作中的时间复杂度为O(logN)。AVL树追求极致的平衡，所以会进行多次旋转。当插入和删除的数量很大时，实现平衡的代价甚至大于使用它所带来的好处。有没有一种平衡二叉搜索树，可以稍微降低平衡，但可以带来更大的整体性能提升？红黑树与AVL树相比，红黑树也是一种平衡二叉搜索树。红黑树似乎并没有那么执着地追求平衡。红黑树只要求最长路径不能超过最短路径的两倍。在红黑树中，节点要么是红色的，要么是黑色的。根节点和叶节点（NIL）都是黑色的，任何路径上都不能连续出现两个红色节点。从根节点开始的所有路径都有相同数量的黑色节点（不包括NIL）。红黑树通过左旋、右旋和变色三种操作来保证一定的平衡。与AVL树相比，红黑树的查询效率较低，但是删除和插入的效率大大提高，整体性能优于AVL树。.并且在实际应用中，红黑树的应用更为广泛。比如HashMap，当链表长度大于8时，会转为红黑树。TreeMap使用红黑树对键值进行排序。在IO多路复用中，epoll使用红黑树来管理Sockets。那么为什么MySQL不用红黑树来组织索引数据呢？如果索引数据可以一次性加载到内存中，那么使用红黑树是没有问题的。问题是索引数据不能一次性加载到内存中，需要分批加载索引数据。假设要查询的数据位于叶子节点上，树高为n。第一次，将根节点加载到内存中，进行一次磁盘IO。一路查询到叶子节点的时候，需要n次IO。当单表数据达到100万条时，树的高度约为log1000000(以2为底)=20。一次磁盘IO平均耗时10ms，20次为0.2秒。如果考虑范围查询、无索引查询、多表联合查询，速度慢得要命。所以，我们现在的首要目标是减少IO的数量，也就是降低树的高度。B树B树也叫B-tree，注意不是B减树，“-”是连字符！！！B树是一种多叉平衡搜索树。当节点总数相同时，B树的高度明显低于二叉树。B树有以下几个重要特点：每个节点可以存储多个元素，节点中的元素是有序的，每个元素也对应一个数据行（当然也可能是主键索引项，或者数据行地址）。父节点中的元素不会出现在子节点中。叶子节点都在同一层，没有指针连接。具有3个叉子的B树是：如您所见，B树的高度被压缩得非常尖锐。另一方面，B树充分利用了程序访问的局部性原则。也就是说，当一个程序访问到磁盘或内存中的一段数据时，其周围的数据将来很有可能会被使用到。因此，B数的每个节点不会只存储一个元素，而是存储多份。我们在查询数据的时候，每进行一次IO，都会将B树的一个节点读入缓存中。这样在访问周边数据的时候，不需要从磁盘读取，而是直接从缓存中读取，缓存命中率大大提高。也许有人会问？如果一个节点存储了大量的元素，从磁盘读取的速度是否随着数量线性增加？答案是不。第一次读取节点时，会进行随机读取，需要先进行磁盘寻道，非常耗时。读完其他元素后，就是顺序读。顺序读取的原因是节点中的元素顺序存储在磁盘上。顺序读取非常快，效率可能是随机读取的数千倍。那么，读取B树上的索引项21的过程是怎样的呢？在节点内部，使用二进制搜索来查找底层指针。看起来B-tree可以有效的解决平衡二叉树io个数过多的问题，似乎已经满足了所有的要求。但是MySQL最终还是采用了B+树而不是B树。相对而言，B树有以下缺点：每个节点不仅存储索引项，还存储特定的数据，所以每个节点可以存储的索引项较少。如果索引项少了，io的数量就会增加。B树不能进行快速范围搜索，需要多次搜索，类似于中序遍历。为了改进B树，后来又提出了B+树。这时B+树又可以读作B+树……B+树有如下特点：非叶子节点只存储索引项，叶子节点既存储索引项又存储具体数据。叶子节点会存放当前所有的索引项，即可以和父节点的索引项重复。叶子节点通过指针连接起来，形成一个有序的双向链表结构。一个成熟的B+树应该有如下风格：由于B+树的叶子节点只存储数据行，所以每次查询都需要加载到叶子节点上。但是B-tree的每个节点都存放着数据行，每次查询不一定非得去叶子节点。那么这时候就会有人提出这样一个问题：B+树每次查询都要深入到叶子节点，那么它的平均查询效率不应该低于B树吗？是的，如果树的高度相同。但实际情况是，当索引项相同时，B+树的高度明显低于B树，因为B+树的非叶子节点比B树可以存储更多的元素，之后all，数据行更少。因此，考虑到iocostplusrange查询，B+树的整体查询效率优于B树，但B+树对单条数据的查询效率低于B树。B+树如何在范围查询中表现出色？先找到范围的下限，直接用叶子节点的指针加载下一个数据块，避免了通过父节点传递。遍历到范围上限后，直接返回所有遍历的数据即可。通过在B+树的叶子节点中重复存储元素，其整体占用的空间其实比B树略高。但是这种浪费的空间可以换来巨大的性能提升，也是很不错的。鉴于B+树的上述优点，MySQL最终采用了B+树作为索引组织方式。这里各种数据结构的对比，直接用最简单明了的方式凸显了每种数据结构的优缺点：
