索引的意义在于提高数据的查询速度,就好像书的目录,通过目录我们可以知道什么内容
在第几页从而直接翻到对应的页码上,而不用一页一页的翻找。
索引的模型
第一种,hash表,通过key的计算得到hashcode从而直接定位到value的位置,不过由于
hash冲突的缘故,hash值相同而value不同的键值对会定位在同一个slot上,并以链表的
形式储存,并且hash表是无序的,所以范围查询的时候比较慢
第二种,有序数组,相对于hash表的缺点,有序数组的的范围查询表现是优秀的,由于是
有序的,通过二分查找能快速定位到目标值,如果是范围查询,往两边顺序遍历即可,但是
有序数组对于数据的增删则效率较低,插入删除一个数据,需要移动后续的所有数据。
第三种,平衡二叉树,特点是每个节点的左儿子小于父节点,父节点又小于右儿子,使其
的查询及更新的时间复杂度皆是0(logn)
mysql N叉树
如果树只有二叉,那么随着数据的增多,树的高度会变得很高,不利于在索引在磁盘的存储,
根据磁盘页的大小和单个索引和索引对应数据的大小,决定mysql索引N叉树具体是多少,假如N是1000,
那么只需4层即能存储1000的3次方的数据,根节点是在内存中,所以最多只需要3次的访问
磁盘便能查到所有数据
索引的维护
B+树为了维持索引的有序性,当有数据增加删除时,便可能会发生数据的挪动,如果此时
由于数据的添加或者删除,而索引所在的页达到存储临界点,那么便会发生页的分裂和页的
合并,影响性能之外,还降低了空间的利用率,所以我们一般都尽量保存主键索引的单调
递增性质,不管是一级索引还是二级索引,叶子节点上放的都是索引字段的数据,所以选择
作为索引的数据,自然越小越好,从而使一页中能存储更多的索引,从而减少页的加载
提升查询效率。
覆盖索引
覆盖索引指的是,我们在二级索引上面找到记录后,因为二级索引上面只有id和索引字段的
数据,如果我们还需要其他字段的信息就必须得去主键索引那棵树上查找,所以我们可以
根据我们所需的字段去建立索引,就无需回表去查询其他数据,同时也需注意索引维护的
成本。
最左前缀原则
本质上,一个联合索引,假设abc,是转成二进制字节数组的,按照abc的顺序逐个从
左往右排好序,所以说来查询一个值,必然你这个值得先把a用了才能用到b,b用了才
能用到c,所以说是最左原则,举个例子,一个联合索引:名字 年龄,你这时候拿名字
来查,那么这个联合索引你就能命中,你拿年龄来查,显然对于名字在前年龄在后的二进制
数组而言,没法查。
索引下推
这是mysql5.6开始引进的优化,用上述的名字年龄来说,你想查询名字是张三的然后年龄
得满足小于18岁的,mysql5.6之前的查询过程是酱紫的:根据名字查到第一个张三之后,
拿主键id去主键索引那颗树上查是不是小于18岁,然后再拿第二个张三的记录去主键索引
树上查以此类推,索引下推就是,我们在查到第一个张三的时候,顺便看一下他的年龄
是不是小于18,如果不是,直接剔除不回表了,满足小于18才会去回表,所以索引下推
能减少查询的回表次数从而提升查询效率