登录 |  注册
首页 >  数据库 · 存储 >  MySql实战精选笔记 >  MySQL数据库索引底层原理:存储方式使用B+树

MySQL数据库索引底层原理:存储方式使用B+树

索引(Index)是帮助MySQL高效获取数据的数据结构,索引的目的在于提高查询效率,就像字典和书籍的目录一样,有了目录,可以帮助你快速查找你需要的内容。可以理解为一个排好序的快速查找数据结构。也就是说,除了数据之外,数据库还维持着一些满足特定查找算法的数据结构,用来加速查询。

优点:

1)提高数据检索效率,降低数据库IO成本;  

2)降低数据排序的成本,降低CPU的消耗

缺点:

索引本身就是一个数据结构,保存了主键和索引字段,并指向实体表的记录,所以也需要占用内存

索引大大提高了查询速度,同时却会降低更新表的速度,如对表进行INSERT、UPDATE和DELETE。 因为更新表时,MySQL不仅要保存数据,还要保存一下索引文件每次更新添加了索引列的字段, 都会调整因为更新所带来的键值变化后的索引信息

索引的类别

从数据结构的角度来看,常用的索引有哈希表、有序数组和搜索树。

哈希索引

通过Hash算法将数据库字段数据转换成定长的Hash值,与这条数据的行指针一并存入Hash表的对应位置;也就是说,哈希表是一种以键 - 值(key-value)存储数据的结构,每次输入待查找的key,就可以得到对应的值value,从而快速确定出要查找的数据。

通常数据库的哈希索引应对哈希冲突(多个不同的key映射到同一个value)的方法是拉链法,即以该value为首建立一个链表,将所有映射到该值的节点都以链表形式串联到后面,因此,如果哈希冲突过于频繁,会非常影响哈希索引的效率。在检索查询时,对待查询的关键字再次执行相同的Hash算法,得到Hash值,到对应Hash表对应位置取出数据即可,如果发生Hash碰撞,则需要在取值时进行筛选。

目前主流的使用哈希索引的引擎较少,主要是Memory。

如图就是一个哈希索引,将ID映射到name

哈希索引.png

因为经过哈希算法 user2 和user4会映射到同一个value,因此需要依次遍历该链表直至找到对应的值。

哈希索引的好处是如果冲突比较少的话,准确搜索会非常快,但是如果冲突比较多的话,时间效率就会比较低。最重要的是,哈希索引不支持前缀搜索和区间查询,也就是说,哈希表只支持等值查询,不支持模糊查询。

有序数组

有序数组,顾名思义,就是按照某种顺序排序好的数组,因此它支持等值查询和范围查询。

有序数组.png

因此,对于给定的ID,可以通过二分的方式迅速找到对应的位置,时间复杂度是 log(n)。 同时,对于范围查询,如果要查身份证号在[ID_card_X, ID_card_Y]区间的 User,可以找到ID_card_X对应的位置,然后向后遍历,直至第一个大于ID_card_Y的元素。因此,在查询上,该方式几乎是最好的数据结构了。但是有序数组最大的缺点是每一次添加元素,都需要对后续的元素进行移动,这个效率是非常低的。

因此,有序数组索引在静态数据上表现非常良好,不适合动态数据。【这个设计的思想还是蛮有趣的,之前面试遇到过设计一个支持多种查询某一年高考信息的数据结构,我便采用了静态数组+HASH的方式,可以通过学号快速访问,也可以通过成绩快速查询区间】

搜索树

数据结构中非常常见的一个树结构就是二叉搜索树。

搜索树.png

二叉搜索树的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子,因此对于精确查询可以以O(logn)的时间复杂度完成,为了维持二叉搜索树,也需要O(logn)的时间复杂度。

但是,在数据库中,通常都采用了多叉搜索树B+树而不是二叉搜索树。

多叉树就是每个节点有多个儿子,儿子之间的大小保证从左到右递增。二叉搜索树的搜索效率通常是最高的,但是,由于数据库中索引通常放置在磁盘中,因此要尽可能减少访问磁盘的数量,因为相较于多读几次内存中的数据的代价,从磁盘中操作的代价要大得多。多叉搜索树就是利用了每次读取磁盘实际上是可以读取到一个磁盘块大小的数据的,因此合理安排节点的数据大小的话,便可以一次磁盘访问将一个节点的数据都存放到内存中,尽管多叉搜索树会多几次访问,但这个时间相较于读取磁盘而言是绝对可以接收的。二叉树的树高度较高,每次查询都需要访问过多节点,即访问数据块过多,而从磁盘随机读取数据块过于耗时。

为了让一个查询尽量少地读磁盘,就必须让查询过程访问尽量少的数据块,因此使用“N 叉”树,N的值具体取决于数据的大小和每次读取的块的大小。

以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。这棵树高是 4 的时候,就可以存 1200 的 3 次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘,N 叉树由于在读写上的性能优点,以及适配磁盘的访问模式,被广泛应用于数据库引擎中。

B+树

B+树是一种广泛地应用于数据库的索引结构,它就是一种特殊的多叉搜索树,InnoDB 存储引擎就是用 B+Tree 实现其索引结构。

在B+Tree中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点上只存储key值信息,这样可以大大加大每个节点存储的key值数量,降低B+Tree的高度。

B+树.png

因此,很显然可以看出,B+树不仅支持较为快速的精准查询,而且可以像有序数组一样实现较快的范围查询,实际上可以当作这是一个支持快速查询的有序链表。同时,B+树支持模糊匹配,即对于姓名而言,只输出姓氏也可以使用该索引进行查询。

当b+树的数据项是复合的数据结构,比如(name,age,sex)的时候,b+数是按照从左到右的顺序来建立搜索树的,比如当(张三,20,F)这样的数据来检索的时候,b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据。因此查询时也支持最左匹配查询。

MyISAM引擎的索引文件和数据文件是分离的。MyISAM引擎索引结构的叶子节点的数据域,存放的并不是实际的数据记录,而是数据记录的地址。索引文件与数据文件分离,这样的索引称为"非聚簇索引",因此在MyISAM中,主索引与辅助索引区别并不大,只是主键索引不能有重复的关键字。

非聚簇索引.png

InnoDB引擎索引结构的叶子节点的数据域,存放的就是实际的数据记录(对于主索引,此处会存放表中所有的数据记录;对于辅助索引此处会引用主键,检索的时候通过主键到主键索引中找到对应数据行),或者说,InnoDB的数据文件本身就是主键索引文件,这样的索引被称为"“聚簇索引”,一个表只能有一个聚簇索引。

InnoDB的主键索引:

InnoDB的主键索引.png

InnoDB的非主键索引:

InnoDB的非主键索引.png

因此,通过InnoDB查询时,如果采用的是非主键索引查询,将先找到对应的主键,然后再去主键索引中查,也就是两次查询,称为“回表查询”。因此,如果能采用主键查询尽量采用主键查询,效率会更高。基于非主键索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。

为什么非主键索引结构叶子节点存储的是主键值?

保证数据一致性和节省存储空间,否则为维护数据的一致性将符出更大的代价,并且将花费巨大的空间存储冗余数据。

为什么推荐使用整型自增主键?

通常来说主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。自增的整型索引在磁盘中会连续存储,在读取一页数据时也是连续,因此对于范围查询将更加高效,同时,在插入或删除数据时,整型自增主键会在叶子结点的末尾建立新的叶子节点,不会破坏左侧子树的结构,减少了索引的重构次数。所以,从性能和存储空间方面考量,自增主键往往是更合理的选择。

哪些情况需要创建索引

1.主键自动建立唯一索引

2.频繁作为查询条件的字段

3.查询中与其他表关联的字段,外键关系建立索引

4.单键/组合索引的选择问题,高并发下倾向创建组合索引

5.查询中排序的字段,排序字段通过索引访问大幅提高排序速度

6.查询中统计或分组字段

哪些情况不要创建索引

1.表记录太少

2.经常增删改的表

3.数据重复且分布均匀的表字段,只应该为最经常查询和最经常排序的数据列建立索引(如果某个数据类包含太多的重复数据,建立索引没有太大意义)

4.频繁更新的字段不适合创建索引(会加重IO负担)

5.where条件里用不到的字段不创建索引

索引相关的MYSQL语法

创建索引:CREATE [UNIQUE] INDEX indexName ON mytable(username(length));

修改表结构(添加索引):ALTER table tableName ADD [UNIQUE] INDEX indexName(columnName)

删除:DROP INDEX [indexName] ON mytable;

使用Alter添加删除索引:

1)ALTER TABLE tableName ADD PRIMARY KEY (column_list): 该语句添加一个主键,这意味着索引值必须是唯一的,且不能为NULL

2)ALTER TABLE tableName ADD UNIQUE index_name (column_list): 这条语句创建索引的值必须是唯一的(除了NULL外,NULL可能会出现多次)。

3)ALTER TABLE tableName ADD INDEX index_name (column_list): 添加普通索引,索引值可出现多次。

4)ALTER TABLE tableName ADD FULLTEXT index_name (column_list)该语句指定了索引为 FULLTEXT ,用于全文索引。

可以以使用 SHOW INDEX 命令来列出表中的相关的索引信息

普通索引和唯一索引怎么选择

假如已经有一个业务保证某列数据唯一性,需要对该列建立索引,那么应该采用普通索引还是唯一索引呢?

比如一个市民系统,每个人都有一个唯一的身份证号,而且业务代码已经保证了不会写入两个重复的身份证号,如果市民系统需要按照身份证号查姓名,就会执行类似这样的 SQL 语句:select name from CUser where id_card = 'xxxxxxxyyyyyyzzzzz';

因此对身份证号这一列建立索引将是非常有用的。

由于身份证号字段比较大,我不建议你把身份证号当做主键,那么现在你有两个选择,要么给 id_card 字段创建唯一索引,要么创建一个普通索引。

从查询和更新的角度分析两个索引的性能差异:

查询

对于查询语句,在索引树上查找的过程是,先通过 B+ 树从树根开始,按层搜索到叶子节点,如果是普通索引,查找到满足条件的第一个记录,将顺序向后继续查询,直至遇到不满足的记录;对于唯一索引,查找到满足条件的记录后,将直接停止检索过程。

不过,由于引擎是按页读取的,所以通常对于普通索引后面符合条件的记录通常也不会增加磁盘读取次数,在内存中的操作时间是较低的,因此二者性能基本无太大差异。

更新

对于更新过程,普通索引将使用一个成为change buffer的机制。

当需要更新一个数据页时,如果数据页在内存中就直接更新,而如果这个数据页还没有在内存中的话,在不影响数据一致性的前提下,InnoDB 会将这些更新操作缓存在 change buffer 中,这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候,将数据页读入内存,然后执行 change buffer 中与这个页有关的操作。

显然,如果能够将更新操作先记录在 change buffer,减少读磁盘,语句的执行速度会得到明显的提升。而且,数据读入内存是需要占用 buffer pool 的,所以这种方式还能够避免占用内存,提高内存利用率。

因此,如果插入数据是不在内存中的,普通索引将采用change buffer机制,这将提高数据库的性能。

对于写多读少的业务来说,页面在写完以后马上被访问到的概率比较小,此时 change buffer 的使用效果最好。这种业务模型常见的就是账单类、日志类的系统。

上一篇: MySQL隔离级别及其原理分析
下一篇: 什么是联合索引/最左前缀/覆盖索引/索引下推
推荐文章
  • mysql只支持一种join算法:Nested-LoopJoin(嵌套循环连接),但Nested-LoopJoin有三种变种:SimpleNested-LoopJoin,IndexNested-LoopJoin,BlockNested-LoopJoin(简单-索引-缓冲区)原理:1.SimpleNe
  • redis是一个内存数据库,一旦断电或服务器进程退出,内存数据库中的数据将全部丢失,所以需要redis持久化 redis持久化就是把数据保存在磁盘上,利用永久性存储介质将数据保存,在特定的时间将保存的数据进行恢复的工作机制redis提供两种持久化机制RDB:存储数据结果,关注点在数据AOF:存储操作
  • 通过SQL的执行过程来介绍MySQL的基础结构.     首先有一个user_info表,表里有一个id字段,执行下面这条查询语句:Select * form user_info where i
  • 索引(Index)是帮助MySQL高效获取数据的数据结构,索引的目的在于提高查询效率,就像字典和书籍的目录一样,有了目录,可以帮助你快速查找你需要的内容。可以理解为一个排好序的快速查找数据结构。也就是
  • 说到数据库事务,大家脑子里一定很容易蹦出一堆事务的相关知识,如事务的ACID特性,隔离级别,解决的问题(脏读,不可重复读,幻读)等等,但是可能很少有人真正的清楚事务的这些特性又是怎么实现的,为什么要有四个隔离级别。今天我们就先来聊聊MySQL中事务的隔离性的实现原理,后续还会继续出文章分析其他特性的
  • 前面我们系统了解了一个查询语句的执行流程,并介绍了执行过程中涉及的处理模块。相信你还记得,一条查询语句的执行过程一般是经过连接器、分析器、优化器、执行器等功能模块,最后到达存储引擎。那么,一条更新语句
学习大纲