mysql索引数据结构详解
本文主要介绍下mysql索引底层数据结构的红黑树,Hash,B树,B+树等概念,以及聚集索引,聚簇索引,稀疏索引到底是什么.
什么是索引
索引是帮助mysql高效获取数据的排好序的数据结构
优点:可以大大加快数据的检索速度,缺点是创建索引和维护索引耗时,同时占物理空间.
索引使用场景:
- 检索查询
- 排序,使用order by将查询结果按照某个字段排序,如果该字段没有建立索引,那么执行计划就会查询出所有的数据,使用外部排序(将数据从磁盘分批读取到内存进行排序,然后合并结果).如果创建了索引,那么直接按照索引的顺序和映射关系逐条取出数据即可.
- 覆盖索引,如果查询的字段都建立了索引,那么会直接在索引表中完成查询,不需要再回表查询.
索引的类型
- 主键索引,一个表只能有一个主键
- 唯一索引,数据列不允许重复,一个表允许多个列创建唯一索引.
alter table table_name add unique(column1,colum2) - 普通索引,基本的索引类型,允许null值,
alter table table_name add index index_name(column1,colum2) - 全文索引
alter table table_name add fulltext(column)
索引的数据结构
mysql的索引的数据结构和具体的存储引擎的实现有关,在mysql中使用较多的索引有Hash索引,B+树索引.我们经常使用的innoDb存储引擎默认的索引实现为B+树索引.对于哈希索引来说,底层的数据结构就是哈希表,因此在大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快.其余大部分场景,建议使用B+树索引.
顺序查找
最基本的查询算法当然是顺序查找（linear search），也就是对比每个元素的方法(全表扫描)，不过这种算法在数据量很大时效率是极低的。
二分查找
比顺序查找更快的查询方式就是二分查找,二分查找的原理是查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到,同样的,当数据比较大时,效率也不是很高
二叉树
二叉排序树的特点是:
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
当数据量比较大时,树的深度就影响了查询的效率,某些数据甚至要遍历到最底层的节点才能找到.比如数据库的自增字段,使用二叉树插入时,这时的数据结构类似于一个链表,遍历的过程其实也就变成了全表扫瞄
Btree索引数据结构
基于二叉树的缺陷,我们可以考虑使用B树,减少树的深度.
如下图所示
B树的特点是:
- 叶节点具有相同的深度,叶节点的指针为空
- 所有的索引元素不重复
- 节点中的数据索引从左到右递增排列
B+tree索引数据结构
如下图所示
B+树是B树的变种,具备以下特点
- 非叶节点不存储data,只存储索引,可以放更多的索引.
- 叶子节点包含所有索引字段.
- 叶子节点用指针链接,可以区间访问的性能.
hash索引数据结构
对索引的key进行一次hash计算,就可以定位出数据存储的位置.
hash索引很多时候要比B+树的索引更高效,但是仅能满足”=”,”in”,不支持范围查询.而且存在hash冲突的问题.
B树和B+树的区别
- 在B树中,可以将键值存放在内部节点和叶子节点,在B+树中,内部节点都是键,没有值,只有叶子节点同时存放键值.
- B+树中,叶子节点有一条链相连,而B树的叶子节点是独立的.
- B树的内部节点同时存储有键值,因此把频繁访问的数据放在靠近根节点的地方会提高查询效率,是B树在特定数据重复多次查询的情景中更高效.
- B+树的内部节点只存放键,不存放值,因此一次的读取,相同的内存大小情况下,B+树可以获取更多的键,能更快的缩小查找范围.而且B+树的叶子节点之间相互关联,因此在一次全数据遍历的情况下,B+树只需要找到最小的节点,然后通过链进行顺序扫描即可,而B树则需要对数的每一层遍历.因此B树只适合随机索引,B+树则可以做到随机索引和顺序检索.
- B+树的空间利用率更高,能减少I/O次数,磁盘读写的代价更低.一般情况下索引是以索引文件存放在磁盘中的,索引查找的过程就产生了磁盘的I/O消耗,B+树的内部节点只有键,因此一次读取到内存,B+树可以读取更多的数据,相对的,IO读写次数也就降低了.而IO读写次数是影响索引效率的最大因素.
- B+查询效率更加稳定.B树索引可能会在非叶子节点结束,越靠近根节点的记录查询时间越短,只要找到关键字即可确定记录的存在.
如以上所说,B树适合随机索引,B+树在随机索引和顺序检索上效率都相当. - 在增删节点时,B+树的效率更高,因此叶子节点以有序链表相连,能提高增删效率.
B+树索引与hash索引对比
- hash索引进行等值查询更快(一般情况下),但是无法进行范围查询,因此他的索引是无序的,但是B+树的所有节点都遵循左节点小于右节点,是有序的,可以进行范围查询.
- hash索引不支持用索引进行排序.
- hash索引不支持模糊查询,多列索引的最左前缀匹配,因为hash函数的不可预测.
- hash索引在任何时候都需要回表查询数据,B+树在聚簇索引,覆盖索引的时候可以只通过索引完成查询.
- hash索引不稳定,当某个键值存在大量重复的时候,会发生hash碰撞,此时效率比较低.
聚簇索引
聚簇索引是一种数据存储方式,InnnoDB索引的实现就是聚簇索引.
- 表数据文件本身就是按照B+树组织的一个索引结构文件.
- 聚集索引的叶子节点包含了完整的数据记录,比如一个叶子节点代表一行记录,那么它的键就是索引字段,比如主键,值就是该行的其他记录.所以Innodb表必须有主键,而且推荐使用整形的自增字段.
- 非主键索引结构的叶子节点存储的是主键,然后根据主键从主键索引中再查找数据.
注意:innodb中,在聚簇索引上创建的索引称为辅助索引,辅助索引访问数据需要进行回表查询.像复合索引,前缀索引,唯一索引,等叶子节点存放的都是主键值.
非聚簇索引并非一定要回表查询,如果索引的叶子节点上已经包含了需要查询的数据,那就不需要回表查询了.
非聚簇索引
非聚簇索引又叫非聚集索引,并不是单独的索引类型,是一种数据存储方式,myisam索引文件和数据文件时分离的,使用的是非聚簇索引,如下图所示
非聚簇索引是将数据存储与索引分开,索引中的叶子节点指向了数据的对应行.myisam存储引擎通过key buffer 把索引缓存到内存中,当需要访问数据时,在内存中先搜索索引,然后根据索引找到磁盘上对应的数据,这也就是索引不再key buffer命中时,速度慢的原因.