一个人至少拥有一个梦想,有一个理由去坚强

心若没有栖息的地方,到哪里都是在流浪

MySQL实站45讲学习笔记—深入浅出索引上

索引作用提高数据查询效率,就像书的目录一样。

索引的常见模式:

提高读写效率的数据结构很多,常见三种比较简单的数据结构:哈希表、有序数组和搜索树。

哈希表:

哈希表是以键-值key-value存储数据的结构。

哈希的思路:把值放在数组里,用一个哈希函数把key换算成一个确定的位置,然后把value放在数据的对应的这个位置。

多个key值经过哈希函数的换算,会出现同一个值的情况。

解决的其中一个方法:拉出一个链表。

为了方便以后理解,引用作者写的例子:

假设你现在维护身份证信息和姓名的表,需要根据身份证信息查找对应的名字,对应哈希索引的示意图如下:

《MySQL实站45讲学习笔记—深入浅出索引上》

假如User2和User4根据身份证号算出的值都是N,则User4和User2用链表连接起来,若现在要查询ID_card_n2的名字,查询步骤:

首先根据ID_card_n2算出值是N,然后再顺序循环链表,找到User2.

注意:图中ID_card_n的值并不是递增的。

优点:增加新的user只需要往后增加,速度比较快。

缺点:区间查询慢。如果找区间[ID_card_n…ID_card_m]则需要全部扫描一遍。

适用场景:哈希表这种结构适用于只有等值查询的场景。比如Memcached及其他一些NoSQL引擎。

数组:有序数组在等值查询和范围查询的场景中的性能都很优秀。

《MySQL实站45讲学习笔记—深入浅出索引上》

身份证号没有重复的情况下,数组按照身份证号递增的顺序存放。若查找ID_card_n2的身份证信息,用二分法可快速查到,并且时间复杂度是O(log(N)).

(关于二分法相关,我后续文章会更新)

优点:查询快。

缺点:插入数据慢。往中间插入一条数据得把插入位置的后面所有数据都往后移动。

适用场景:有序数组适用于静态存储引擎。也就是不会再更新的数据。

二叉搜索树:

《MySQL实站45讲学习笔记—深入浅出索引上》

二叉搜索树特点:每个节点的左儿子小于父节点,父节点又小于右儿子。

若要查询ID_card_n2的话,搜索顺序为:UserA->UserC->UserF->User2,根据这个路径得到。时间复杂度为O(log(n)).

为了维持O(log(n))的查询复杂度,需要保证这棵树是平衡二叉树。则更新的时间复杂度也要为O(log(n)).

附:多叉树,每个节点有多个儿子,儿子之间的大小保证从左到右递增。

二叉树的搜索效率是最高的,但是实际上大多数数据库存储并不使用二叉树。原因:索引不止存在内存中,还要写在磁盘上。

为了查询尽量少读磁盘,则必须让查询过程访问尽量少的数据块。那么就不应该使用二叉树,而是要“N叉”树。这里“N叉”树中的“N”取决于数据块。

N叉树由于在读写上的性能优点,以及适配磁盘的访问模式,已被广泛应用在数据库引擎中。

InnoDB的索引模型:

索引组织表:在InnoDB中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表。

InnoDB使用B+树索引模型,所以数据都是存储在B+树中。

每一个索引在InnoDB里面对应一颗B+树。

主键列为ID的表,表中有字段k,并且k上有索引。

建表语句:

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中R1-R5的(ID,k)值分别为(100,1)、(200,2),(300,3),(500,5),(600,6),两棵树示意图如下:

《MySQL实站45讲学习笔记—深入浅出索引上》

InnoDB的索引组织结构

索引类型分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据。在InnoDB里,主键索引也被称为聚簇索引(clustered index).

非主键索引的叶子节点内容是主键的值。在InnoDB里,非主键索引也被称为二级索引(secondary index)

基于主键索引和普通索引的查询区别:

  • 如果语句是select * from T where ID=500,即主键查询方式,则只需要搜索ID这课B+树。
  • 如果语句是select * from T where k=5,即普通索引查询方式,则需要先搜索k索引树,得到ID的值为500,再到ID索引树搜索一次。这个过程称为回表。

基于非主键索引的查询需要多扫描一棵索引树。因此,在应用中应该尽量使用主键查询。

索引维护

B+树为了维护索引有序性,在插入新值的时候需要做必要的维护。以上面图为例,如果插入新的行ID值为700,则只需要在R5后面插入一个新记录。如果新插入的ID值为400,就相对麻烦了,需要逻辑上挪动后面的数据,空出位置。

而更糟的情况是,如果R5所在的数据页已满了,根据B+树的算法,这时需要申请一个新的数据页,然后挪动部分数据过去。这个过程称为页分裂。在这种情况下,性能自然受到影响。

除了性能外,页分裂操作还影响数据页的利用率。原本放在一个页的数据,现在分在两个页中,整体空间利用率降低大约50%。

当然有分裂就有合并。当相邻两个页由于删除了数据,利用率很低之后,会将数据页做合并。合并的过程可以说是分裂过程的逆过程。

总之,InnoDB使用B+树结构,B+树能够很好的配合磁盘的读写特性,减少单次查询磁盘的访问次数。

由于InnoDB是索引组织,一般情况下建议创建自增索引,这样非主键索引占用的空间最小。

 

总结:

1.索引的作用:提高数据查询效率
2.常见索引模型:哈希表、有序数组、搜索树
3.哈希表:键 – 值(key – value)。
4.哈希思路:把值放在数组里,用一个哈希函数把key换算成一个确定的位置,然后把value放在数组的这个位置
5.哈希冲突的处理办法:链表
6.哈希表适用场景:只有等值查询的场景
7.有序数组:按顺序存储。查询用二分法就可以快速查询,时间复杂度是:O(log(N))
8.有序数组查询效率高,更新效率低
9.有序数组的适用场景:静态存储引擎。
10.二叉搜索树:每个节点的左儿子小于父节点,父节点又小于右儿子
11.二叉搜索树:查询时间复杂度O(log(N)),更新时间复杂度O(log(N))
12.数据库存储大多不适用二叉树,因为树高过高,会适用N叉树
13.InnoDB中的索引模型:B+Tree
14.索引类型:主键索引、非主键索引
主键索引的叶子节点存的是整行的数据(聚簇索引),非主键索引的叶子节点内容是主键的值(二级索引)
15.主键索引和普通索引的区别:主键索引只要搜索ID这个B+Tree即可拿到数据。普通索引先搜索索引拿到主键值,再到主键索引树搜索一次(回表)
16.一个数据页满了,按照B+Tree算法,新增加一个数据页,叫做页分裂,会导致性能下降。空间利用率降低大概50%。当相邻的两个数据页利用率很低的时候会做数据页合并,合并的过程是分裂过程的逆过程。
17.从性能和存储空间方面考量,自增主键往往是更合理的选择。

思考题:
如果删除,新建主键索引,会同时去修改普通索引对应的主键索引,性能消耗比较大。
删除重建普通索引貌似影响不大,不过要注意在业务低谷期操作,避免影响业务。

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注