究极无敌细节版 Mysql索引 _生活百科

参考了：https://www.jianshu.com/p/ace3cd6526c4推荐up主https://space.bilibili.com/377905911推荐书籍《mysql是怎样运行的》推荐极客时间《MySQL实战45讲》——林晓斌系列文章目录和关于我
一丶什么是索引索引是存储引擎快速找到记录的一种数据结构。数据库中的数据可以理解成字典中的单词，而索引就是目录，显而易见这是一种空间换时间的做法，目录占用了空间，但是加快了我们找到单词的速度，正如索引需要空间存储，但是利用索引我们可以快速的找到想要的数据。
InnoDB存储引擎存在几种常见的索引：

B+树索引
全文索引
哈希索引

本文主要讨论B+树索引
二丶索引的数据结构可以加快查找速度的数据结构很多，为什么mysql使用B+树来实现昵，换句话说哈希表，有序数组，跳表，平衡二叉搜索树，B-树等都可以优化搜索效率，为什么偏偏使用B+树
1.哈希表哈希表，可以联想Java中的HashMap，在HashMap源码学习中，我们了解到Hash表的数据结构。如下图

文章插图
哈希表通过hash算法将key映射到数组对应的下标进行存储，不可避免的会产生hash冲突（多个不同的key散列到相同的数组下标中），解决hash冲突常用拉链法，顾名思义，就是把相同hash值的节点组成链表串起来。在根据key查找value的过程中，只需要再次使用相同的hash算法那么就能拿到对应的数组下表，然后遍历链表找到目标值即可,查找的效率是o(1) 。

明明存在链表需要遍历为什么说时间复杂度o(1)首先hash算法计算是常数时间，hash表会在需要的时候进行扩容，维持链表长度尽量在一个常数范围，从而保证遍历常数个链表节点

mysql中存在自适应哈希索引，由innodb存储引擎自己控制，利用查找O(1)的性质优化等值查询。我们可以看出，hash表并不适合范围查询，对于Id<10这种范围查询只能遍历hash表中每一个数据，相当于要进行一次全表扫描。我还有一个想法：从扩容的角度看，每次扩大数组大小后都需要移动元素到新的数组空间中，这部分的复制移动的开销也许也是hash表不合适的原因（redis为了解决这个问题，使用渐进式hash的方式，在扩容的时候生成更大的数组，但不是一次移动所以数据，而是插入的新元素都放到新数组，老数组使用到的数据才会慢慢移动到新数组）redis基于内存的数据库都需要通过渐进式hash优化扩容操作，基于磁盘的mysql若使用hash将惨不忍睹
2.有序数组有序数组就是数据中元素有序，正因为有序，所以其在范围查找上非常优秀，正因为要维持有序，在更改数据的时候，也许需要移动大量数组元素（比如插入一个较小的值，大于此值的数据都需要后移动），所以有序数据只适用于静态数据（比如2020年人口信息，这种不会改变的数据）
3.跳表

文章插图
为了解决有序数组需要移动元素的问题，我们可以使用链表来维护元素，从而使更改元素效率为o(1)，但是链表的查找非常慢。由于链表整体是有序的，那么我们可以使用二分查找优化查找效率，如上我们建立多级的节点，在查找的时候我们首先通过多级的索引依次找到最下层。对于范围查找，由于底层数据是有序的，查找id<7的数组，首先我们找到id=7然后向左遍历集合（可以把跳表最下面一层优化为双向链表，从而让范围查找速度也很快）