索引简单来说,可以被认为是书的目录一样的东西
首先开篇点题,说一下MySql中索引采用的是B+树的数据结构,Mysql会采用B+树作为数据接口,必然是采用b+树有利于我们提高查询效率,至于为啥没选择其他的数据结构去实现索引,是因为其他的数据结构,例如哈希表 有序的数组 搜索树不如其的效率之高,至于为啥不如其高,可以简单的分析下
1.哈希表,是一种以key-value为存储数据的数据格式,通过key来查询到value,但是会出现多个问题,如果采用hash算法来进行处理key,会出现多个key相同的情况,为此可以采用拉链法来进行解决
这样直接利用的话,会出现如果查找一个key,可能出现返回一个链表,还需要进行链表上搜索
而且由于hash不是有序的,所以哈希索引区间查询是不合适的
哈希表这种数据结构只适合等值查询的场景,比如Memcached或者其他引擎
2.有序数组,在等值查询和区间查询的查询性能都非常的合适
那么在这个有序数组的查询就是很快查到的,时间复杂度是 O(log(N))
只是看查询的话,有序数组的效率非常高,但是插入一条数据的话,那么会将后面所有的数据都往后挪动
有序数组只适合存储静态存储的引擎
3.搜索树
比如二叉搜索树,就是经典的数据结构
但是维持这样一颗完美的平衡二叉树很困难,更新的时间复杂度是O(log(N))
但是树可以是二叉,当然也可以是多叉树,就是一个节点有多个子节点,从左到右递增,那这种数据结构非常适合索引这种数据结构
因为索引还要保存在磁盘上
为了减少查询索引过程中需要查询磁盘的数据次数,那么采用了N叉树,N叉树种的N取决于数据块的大小
常见的InnoDB的一个整数字段索引为例,N为1200
于是N叉树在读写上的性能优点,可以广泛应用在数据库引擎之中
而且数据库技术发展到今天,还加上了跳表 LSM树等数据结构
在InnoDB的索引模型汇总
表示根据主键顺序以索引的形式存放,这种存储方式的表为索引组织表,
每一个索引在InnoDB里面对应一个B+树
假设有一个主键列为ID的表,表上有字段K, k有索引
插入5个数据
对应生成的两个索引树
上面的索引可以分为主键索引和非主键索引
主键索引存储的是整行的数据,主键索引又名聚簇索引
非主键索引存储的是主键的值,索引又被称为了二级索引
两者在查询上的区别为
select * from T where ID =500 为主键查询方式,直接搜索ID这个数,然后从主键索引中取出所有的值
但是如果查询k
select * from T where k = 5;会先进行一次搜索,在K索引上找到对应的主键ID,搜索完成后在ID索引上再搜索一次,回表操作
于是,建议尽可能的使用主键索引
那么,mysql是如何维护索引的?
在维护索引的有序性方面,Mysql做了如下的处理,如果插入的为700,那么直接放在600之后,如果插入一个400,则需要让500和600后移一位
而且,一个数据页是有上限的,如果一个数据页已经满了,那么会在插入的时候分裂出一个新的,称为页分裂,页分裂也会降低数据页的利用率,当然如果页删除了数据利用率低到一种程度后,会进行页的合并
那么,另外一个比较重要的思考问题就是如何选择主键,需要分析下什么时候什么键适合做主键
自增主键使用和理解比较容易,就是不指定ID的时候,自动获取下一个ID作为ID值
使用了自增组件,不会出现插入的情况,只会依次的往后传递,非常适合作为主键,
而使用业务逻辑的字段作为主键,会导致插入的无序性,不容易做主键.
除此外,还能考虑下存储空间
如果主键的长度过长,那不建议做主键,因为占用的二级索引的叶子节点的大小会很大
显然,主键长度过小,普通索引的叶子节点就越小,普通索引占用的空间越小
所以说自增主键很合适,但是有些场景下,如果只有一个值,或者这个值是唯一的,可以用来作为主键索引
假设一个一个执行语句,选在3到5之间的数
Select * from T where k between 3 and 5;
那么执行语句为,由k索引树上找到k=3的ID,然后回主键索引上查找到相关的数据
然后找到下一条并且回表,最后直到超过范围
这个从二级索引树到主键索引树回去搜索的过程称为回表操作
那么就可以从主键索引上下手,避免进行回表操作拖累查找索引效率
首先第一条就可以考虑使用覆盖索引,就是索引树K已经包含所要查找的数据
对于这种情况,可以对应着现实的情况,那就是市民身份上的信息
首先是,一个表上,有必要将身份证号和名字建立联合索引?
如果查询身份证的时候经常会查询到名字,那么可以建立联合索引,但是为了维护这个索引可能会造成额外的负担,这就是DBA应该先考虑的工作
然后可以考虑最左前缀原则
B+树这种索引数据结构,支持最佳左前缀原则进行匹配定位
为了解释这种概念,可以拿一个联合索引来说
联合索引name和age作为字段的话,
可以直接在其中查找 name like 张%
这样可以从ID3之后匹配,直到遇到一个不符合的
那么可以在搜索的时候利用最佳左前缀匹配来进行快速定位
但需要注意,在建立联合索引的时候,需要合理的安排索引中的字段顺序
也就是如果通过调整顺序,可以少维护一个索引,那么这个顺序就是需要优先考虑的
假设上面的name和age
name比age大,需要建立一个联合索引
建议建立一个 name,age的索引,name放前面而且比较大,然后和一个age的单独索引
最后考虑索引下推的问题
对于索引搜索过程中,对于不符合搜索要求的数据,假设差一个”张”如果不符合,在MySql 5.6之前,只能一个个的回表,然后找出数据行比对,在5.6之后,可以在二级索引树中直接进行判断,而不需要回表了
最后一提,在建立索引的过程中,如果是一个二级索引,可以考虑直接
alter table T drop index x
后在重建这个索引 alter table T add index(k)