在Java面试中必问mysql，问mysql的时候索引也是必问，可见索引有多么重要。简单的说索引是一种为了提高数据检索效率的一种数据结构。
索引的常⻅模型
索引的出现是为了实现数据检索的高效，只所以引入索引的概念是为因为能实现数据高效索引的数据结构很多，我们先看一下常见的三种数据结构哈希表、有序数组和搜索树。
1、 哈希表是一种key-value键值对，输入key就可以找到value的值。实现一个哈希表很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。不可避免地，多个key值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。假设你现在在维护一个订单信息和订单号sn的表，需要根据订单号sn查找订单信息。此时对应的哈希索引如下图：截屏2020-07-28 下午11.20.32.png
![47\_1.png][47_1.png]订单m和订单n算出来的都是m，但是没关系，后面跟的是一个链表，如果要查询order\_m首先计算order\_sn算出为m*时间复杂度为O(1)再遍历后面的链表时间复杂度为O(n)*,这种情况对于取区间的值就比较慢了，必须一个一个的遍历。所以**哈希表只适合等值查询的场景**。
2、 有序数组在等值查询和范围查询场景中的性能就都非常优秀，但是有序数组索引只适用于静态存储引擎，因为维持有序的成本非常高，每次插入和删除都需要维持有序，下标需要移动。如果仅仅看查询效率，有序数组就是最好的数据结构了。在需要更新数据的时候就麻烦了，你往中间插入一个记录就必 须得挪动后面所有的记录，成本太高。截屏2020-07-28 下午11.38.13.png
![47\_2.png][47_2.png]
3、 跳表 skiplist，我们知道链表在每次查找的时候都需要遍历一次表，我们能不能改造一下链表提高检索的效率，可以使用索引的思想对链表进行改造，将部分关键提取出来当做关键节点，如果检索效率还是太低，再将关键节点的数据取出来当关键节点的关键节点。image-20200729230340082.png
![47\_3.png][47_3.png]
4、 二叉搜索树，如果我们有个用户表用二叉搜索树实现的话如下图:截屏2020-07-29 上午12.00.29.png
![47\_4.png][47_4.png]二叉搜索树的特点是:每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查ID\_card\_n2的话，按照图中的搜索顺序就是按照UserA -> UserC -> UserF -> User2这个路径得到。这个时间复杂度是O(log(N))。
用一张动图来表示搜索过程假设在这个树中搜索20流程如下: QQ20200729-001928-HD.gif
![47\_5.png][47_5.png]
当然为了维持O(log(N))的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是O(log(N))。所谓维持平衡就是要避免出现类似于链表的树，要让数据分布在树的两侧。树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。你可以想象一下一棵100万节点的平衡二叉树，树高20。一次查询可能需要访问20个数据块。\*为什么树高是1就要io一次？因为每一次io只能取出一个节点的数据对于二叉树也就是2个，只取两个因为要根据取出来的数据的指针去获取后面的数据，除非后面节点的数据刚好和硬盘中取出的数据相邻。\*为了减少io成本就应该把树高降低，所以数据库使用了N插树。在一次io中查出来一个节点的数据包含N个指针，从而降低io次数。
InnoDB 的索引模型
InnoDB使用了B+树索引模型，B+树是在搜索树的基础上改进的。为了方便理解我们就把模型简化为二叉树，树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来有点想跳表。
改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中 的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。但是如果在千万上亿级别的数据中构建索引，如果索引都放入内存中尽管检索非常好但是也是非常耗费内存的一件事，所以不能不索引全部放内存中，放硬盘就涉及到了io性能的问题，前面我们提到了降低树高，将二叉变为M叉，这个M的数值放多少合适？不管是内存中的数据，还是磁盘中的数据，操作系统都是按页(一页大小通常是4KB，这个值可以通过getconfig PAGE_SIZE命令查看)来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次IO操作。所以，我们在选择m大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘IO操作。对于一个B+树来说，m值是根据页的大小事先计算好的，也就是说，每个节点最多只能有m个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘IO操作。当出现超过m的情况我们就进行列表操作，裂变之后父节点也会超过m，同样的操作我们将父节点也进行一遍。这种级联反应会从下往上，一直影响到根节点。我们用一个动图(图中的m为3)来表示:QQ20200729-234642-HD.gif 
B+树的特点：
- 每个节点中子节点的个数不能超过m，也不能小于m/2;
- 根节点的子节点个数可以不超过m/2，这是一个例外;
- m叉树只存储索引，并不真正存储数据，这个有点儿类似跳表; 通过链表将叶子节点串联在一起，这样可以方便按区间查找;
- 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。
“N叉树”的N值在MySQL中是可以被人工调整的么?
5、6以后可以通过page大小来间接控制。
