3. 高性能索引
高性能索引
生活中的索引
MySQL 官方对索引的定义为:索引(Index)是帮助 MySQL 高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。
图书馆的图书,字典的索引页
MySql 中的索引
MySql 中的索引其实也是这么一回事,我们可以在数据库中建立一系列的索 引,比如创建主键的时候默认会创建主键索引,上图是一种 BTREE 的索引。每一 个节点都是主键的 ID
InnoDB 存储引擎支持以下几种常见的索引:B 树索引、全文索引、哈希索 引,其中比较关键的是 B 树索引,其他的索引我们也会在本课程中穿插讲解。
HashMap 适合做数据库索引吗?
1、hash 表只能匹配是否相等,不能实现范围查找;
2、当需要按照索引进行 order by 时,hash 值没办法支持排序;
3、组合索引可以支持部分索引查询,如(a,b,c)的组合索引,查询中只用到了a和 b 也可以查询的,如果使用 hash 表,组合索引会将几个字段合并 hash,没办法支持部分索引;
4、当数据量很大时,hash 冲突的概率也会非常大。
B Tree
B 树索引就是传统意义上的索引,这是目前关系型数据库系统中查找最常用和最为有效的索引。B 树索引的构造类似于二叉树,根据键值(Key Value)快速 找到数据。注意 B 树中的 B 不是代表二叉(binary),而是代表平衡(balance),因 为 B 树是从最早的平衡二叉树演化而来,但是 B 树不是一个二叉树。
在了解 B 树索引之前先要知道与之密切相关的一些算法与数据结构,这有 助于我们更好的理解 B 树索引的工作方式,因为 B 树是通过二叉查找树,再由 平衡二叉树,B 树演化而来。
二分查找
略
二叉树系列
二叉树
二叉查找(搜索)树
平衡二叉树(AVL-树)
B 树
B 树的定义
B 树和二叉树、平衡二叉树一样,都是经典的数据结构。B 树由 B 树和索引顺序访问方法演化而来,但是在现实使用过程中几乎已经没有使用 B 树的情况 了。
B 树的定义在很多数据结构书中都能找到,非常复杂,我们概略它的定义:
B 树是 B 树的一种变形形式,B 树上的叶子结点存储关键字以及相应记录 的地址,叶子结点以上各层作为索引使用。一棵 m 阶的 B 树定义如下:
-
每个节点最多可以有 m 个元素;
-
除了根节点外,每个节点最少有 (m/2) 个元素;
-
如果根节点不是叶节点,那么它最少有 2 个孩子节点;
-
所有的叶子节点都在同一层;
-
一个有 k 个孩子节点的非叶子节点有 (k-1) 个元素,按升序排列;
-
某个元素的左子树中的元素都比它小,右子树的元素都大于或等于它;
-
非叶子节点只存放关键字和指向下一个孩子节点的索引,记录只存放在叶子节点中;
-
相邻的叶子节点之间用指针相连
B 树的变体为 B树,在 B 树的非根和非叶子结点再增加指向兄弟的指针; B树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为 2/3(代 替 B 树的 1/2)。
我们概要的了解下 B 树和 B 树。
B 树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在 B 树中, 所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点 指针进行连接。比如:
从上图我们可以归纳出 B 树的几个特征,在 B 树的简要定义中其实已经包 括了:
1、相同节点数量的情况下,B 树高度远低于平衡二叉树;
2、非叶子节点只保存索引信息和下一层节点的指针信息,不保存实际数据 记录;
3、每个叶子页(LeafPage)存储了实际的数据,比如上图中每个叶子页就 存放了 4 条数据记录,当然可以更多,叶子节点由小到大(有序)串联在一起, 叶子页中的数据也是排好序的;
4、索引节点指示该节点的左子树比这个索引值小,而右子树大于等于这个 索引值。
***注意:***叶子节点中的数据在物理存储上完全可以是无序的,仅仅是在逻辑 上有序(通过指针串在一起)。
B 树的插入
B 树的插入必须保证插人后叶子节点中的记录依然排序,同时需要考虑插 入到 B 树的三种情况,每种情况都可能会导致不同的插入算法。
略
B 树的删除
B 树使用填充因子(fill factor)来控制树的删除变化,50%是填充因子可设 的最小值。B 树的删除操作同样必须保证删除后叶子节点中的记录依然排序,同 插入一样,B 树的删除操作同样需要考虑三种情况,与插入不同的是,删除会加 入填充因子的考量。
叶子节点大于填充因子,中间节点大于填充因子,直接将记录从叶子节点 删除,如果该节点还是 IndexPage 的节点,用该节点的右节点代替。
叶子节点大于填充因子,中间节点小于填充因子,合并叶子节点和它的兄 弟节点,同时更新 Index Page。
叶子节点小于填充因子,中间节点小于填充因子,
略
磁盘和 B 树
为什么关系型数据库都选择了 B 树,这个和磁盘的特性有着非常大的关系。
如果我们简化一下,可以这么看
一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必 须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动。(但可以平移)
盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道, 所有半径相同的磁道组成一个柱面(是面不是柱,所以说的是一个盘片)。磁道被沿半径线划分成一个个小的段,每个 段叫做一个扇区,每个扇区是磁盘的最小存储单元也是最小读写单元。现在磁盘 扇区一般是 512 个字节~4k 个字节。
磁盘上数据必须用一个三维地址唯一标示:柱面号、盘面号、扇区号。****(x,y,z坐标)
读/写磁盘上某一指定数据需要下面步骤:
(1) 首先移动臂根据柱面号使磁头移动到所需要的柱面上,这一过程被称为定位或查找。 (查找柱面, x)
(2) 所有磁头都定位到磁道上后(定位),这时根据盘面号来确定指定盘面上的具体磁道。(指定盘面y, 因为所有盘面都有磁头, 所以不在需要查找)
1,2称为寻道(seek)
(3) 盘面确定以后,盘片开始旋转,将指定块号的磁道段移动至磁头下。 经过上面步骤,指定数据的存储位置就被找到。这时就可以开始读/写操作 了。(寻找扇区, 圆道的z)(rotation)
3称为寻址(扇区的地址)
可以看见,磁盘读取依靠的是机械运动,分为寻道时间、旋转延迟、传输时间三个部分,这三个部分耗时相加就是一次磁盘 IO 的时间,一般大概 9ms 左 右。寻道时间(seek)是将读写磁头移动至正确的磁道上所需要的时间,这部分时间代价最高;旋转延迟时间(rotation)是磁盘旋转将目标扇区移动到读写磁 头下方所需的时间,取决于磁盘转速;数据传输时间(transfer是完成传输数 据所需要的时间,取决于接口的数据传输率,在纳秒级,远小于前两部分消耗时间。磁盘读取时间成本是访问内存的几百倍到几万倍之间。
为了提高效率,要尽量减少磁盘 I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存,这个称之为预读。这样做的理论依 据是计算机科学中著名的局部性原理:
当一个数据被用到时,其附近的数据也通常会马上被使用。 程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间), 一般来说,磁盘的顺序读的效率是随机读的 40 到 400 倍都有可能,顺序写是随 机写的 10 到 100 倍(SSD 盘则差距要小的多,顺序读写的效率是随机读写的 7 到 10 倍,但是有评测表明机械硬盘的顺序写性能稍优于 SSD。总的来说 Mysql 数据库如果由硬盘由机械的换成 SSD 的,性能会有很大的提升),因此对于具有 局部性的程序来说,预读可以提高 I/O 效率。
预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块, 硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储 块称为一页,页大小通常为 4k 当然也有 16K 的,主存和磁盘以页为单位交换数 据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁 盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内 存中,然后异常返回,程序继续运行。
按照磁盘的这种性质,如果是一个页存放一个 B 树的节点,自然是可以存 放很多的数据的,比如 InnoDB 里,默认定义的 B 树的节点大小是 16KB,这就是 说,假如一个 Key 是 8 个字节,那么一个节点可以存放大约 1000 个 Key,意味 着 B 数可以有 1000 个分叉。同时 InnoDB 每一次磁盘 I/O,读取的都是 16KB 的 整数倍的数据。也就是说 InnoDB 在节点的读写上是可以充分利用磁盘顺序 IO 的 高速读写特性。
同时按照 B 树逻辑结构来说,在叶子节点一层,所有记录的主键按照从小 到大的顺序排列,并且形成了一个双向链表。同一层的非叶子节点也互相串联, 形成了一个双向链表。那么在实际读写的时候,很大的概率相邻的节点会放在相 邻的页上,又可以充分利用磁盘顺序 IO 的高速读写特性。所以我们对 MySQL 优 化的一大方向就是尽可能的多让数据顺序读写,少让数据随机读写。
总结 B 树的作用
-
在块设备上,通过 B 树可以有效的存储数据
-
所有记录都存储在叶子节点上,非叶子(non-leaf)存储索引(keys)信息,而且记录按照索引列的值由小到大排好了序。
-
B 树含有非常高的扇出(fanout),通常超过 100,在查找一个记录 时,可以有效的减少 IO 操作;
Tips:
扇出 是每个索引节点(Non-LeafPage)指向每个叶子节点(LeafPage)的指针;
扇出数 = 索引节点(Non-LeafPage)可存储的最大关键字个数 1
InnoDB 中的索引
InnoDB 中的索引自然也是按照 B 树来组织的,前面我们说过 B 树的叶子节 点用来放数据的,但是放什么数据呢?索引自然是要放的,因为 B 树的作用本 来就是就是为了快速检索数据而提出的一种数据结构,不放索引放什么呢?但是 数据库中的表,数据才是我们真正需要的数据,索引只是辅助数据,甚至于一个 表可以没有自定义索引。InnoDB 中的数据到底是如何组织的?
聚集索引/聚簇索引
InnoDB 中使用了聚集索引,就是将表的主键用来构造一棵 B 树,并且将整 张表的行记录数据存放在该 B 树的叶子节点中。也就是所谓的索引即数据,数 据即索引。由于聚集索引是利用表的主键构建的,所以每张表只能拥有一个聚集 索引。
聚集索引的叶子节点就是数据页。换句话说,数据页上存放的是完整的每行 记录。因此聚集索引的一个优点就是:通过过聚集索引能获取完整的整行数据。 另一个优点是:对于主键的排序查找和范围查找速度非常快。
如果我们没有定义主键呢?MySQL 会使用唯一性索引,没有唯一性索引, MySQL 也会创建一个隐含列 RowID 来做主键,然后用这个主键来建立聚集索引。
辅助索引/二级索引
上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用,因为 B 树 中的数据都是按照主键进行排序的,那如果我们想以别的列作为搜索条件怎么 办?我们一般会建立多个索引,这些索引被称为辅助索引/二级索引。
对于辅助索引(Secondary Index,也称二级索引、非聚集索引),叶子节点 并不包含行记录的全部数据。叶子节点除了包含键值以外,每个叶子节点中的索 引行中还包含了一个书签( bookmark)。该书签用来告诉 InnoDB 存储引擎哪里可 以找到与索引相对应的行数据。因此 InnoDB 存储引擎的辅助索引的书签就是相 应行数据的聚集索引键。
比如辅助索引 index(node),那么叶子节点中包含的数据就包括了(主键、 note)。
回表
辅助索引的存在并不影响数据在聚集索引中的组织,因此每张表上可以有多 个辅助索引。当通过辅助索引来寻找数据时,InnoDB 存储引擎会遍历辅助索引 并通过叶级别的指针获得指向主键索引的主键,然后再通过主键索引(聚集索引) 来找到一个完整的行记录。这个过程也被称为回表。
联合索引/复合索引
注意这里和联合主键的区别,联合主键是很有可能违反第二范式的
前面我们对索引的描述,隐含了一个条件,那就是构建索引的字段只有一个, 但实践工作中构建索引的完全可以是多个字段。所以,将表上的多个列组合起来 进行索引我们称之为联合索引或者复合索引,比如 index(a,b)就是将 a,b 两个 列组合起来构成一个索引。
千万要注意一点,建立联合索引只会建立 1 棵 B 树,多个列分别建立索引 会分别以每个列则建立 B 树,有几个列就有几个 B 树,比如,index(note)、 index(b),就分别对 note,b 两个列各构建了一个索引。
index(note,b)在索引构建上,包含了两个意思:
1、先把各个记录按照 note 列进行排序。
2、在记录的 note 列相同的情况下,采用 b 列进行排序
覆盖索引/索引覆盖(是索引查找的一种行为,不是索引的一种类型,可以避免回表)
既然多个列可以组合起来构建为联合索引,那么辅助索引自然也可以由多个 列组成。
InnoDB 存储引擎支持覆盖索引(covering index,或称索引覆盖),即从辅 助索引中就可以得到查询的记录,而不需要查询聚集索引中的记录。使用覆盖索 引的一个好处是辅助索引不包含整行记录的所有信息,故其大小要远小于聚集索 引,因此可以减少大量的 IO 操作。所以记住**,覆盖索引并不是索引类型的一种。**
所以我们可以认为主键索引本表的数据总是索引覆盖的特殊类型,总是需要回表的
自适应哈希索引
InnoDB 存储引擎除了我们前面所说的各种索引,还有一种自适应哈希索引, 我们知道 B 树的查找次数,取决于 B 树的高度,在生产环境中,B 树的高度一般 为 3~4 层,故需要 3~4 次的 IO 查询。
所以在 InnoDB 存储引擎内部自己去监控索引表,如果监控到某个索引经常 用,那么就认为是热数据,然后内部自己创建一个 hash 索引,称之为自适应哈 希索引( Adaptive Hash Index,AHI),创建以后,如果下次又查询到这个索引, 那么直接通过 hash 算法推导出记录的地址,直接一次就能查到数据,比重复去 B tree 索引中查询三四次节点的效率高了不少。
InnoDB 存储引擎使用的哈希函数采用除法散列方式,其冲突机制采用链表 方式。注意,对于自适应哈希索引仅是数据库自身创建并使用的,我们并不能对 其进行干预。通过命令 show engine innodb status\G 可以看到当前自适应哈希 索引的使用状况,如:
show engine innodb status \G
mysql> show engine innodb status \G
*************************** 1. row ***************************
Type: InnoDB
Name:
Status:
=====================================
2021-12-09 07:02:40 139781660538624 INNODB MONITOR OUTPUT
=====================================
Per second averages calculated from the last 50 seconds
-----------------
BACKGROUND THREAD
-----------------
srv_master_thread loops: 13 srv_active, 0 srv_shutdown, 37284 srv_idle
srv_master_thread log flush and writes: 0
----------
SEMAPHORES
----------
OS WAIT ARRAY INFO: reservation count 22
OS WAIT ARRAY INFO: signal count 20
RW-shared spins 0, rounds 0, OS waits 0
RW-excl spins 0, rounds 0, OS waits 0
RW-sx spins 0, rounds 0, OS waits 0
Spin rounds per wait: 0.00 RW-shared, 0.00 RW-excl, 0.00 RW-sx
------------
TRANSACTIONS
------------
-------------------------------------
INSERT BUFFER AND ADAPTIVE HASH INDEX
-------------------------------------
Ibuf: size 1, free list len 0, seg size 2, 0 merges
merged operations:
insert 0, delete mark 0, delete 0
discarded operations:
insert 0, delete mark 0, delete 0
Hash table size 34679, node heap has 2 buffer(s)
Hash table size 34679, node heap has 0 buffer(s)
Hash table size 34679, node heap has 0 buffer(s)
Hash table size 34679, node heap has 2 buffer(s)
Hash table size 34679, node heap has 3 buffer(s)
Hash table size 34679, node heap has 3 buffer(s)
Hash table size 34679, node heap has 2 buffer(s)
Hash table size 34679, node heap has 7 buffer(s)
0.00 hash searches/s, 0.00 non-hash searches/s ##### here
---
LOG
---
哈希索引只能用来搜索等值的查询,如 SELECT* FROM table WHERE index co=xxx。而对于其他查找类型,如范围查找,是不能使用哈希索引的,
因此这里出现了 non- hash searches/s 的情况。通过 hash searches: non- hash searches 可以大概了解使用哈希索引后的效率。
由于 AHI 是由 InnoDB 存储引擎控制的,因此这里的信息只供我们参考。不 过我们可以通过观察 SHOW ENGINE INNODB STATUS 的结果及参数 innodb_adaptive_hash_index 来考虑是禁用或启动此特性,默认 AHI 为开启状态。
什么时候需要禁用呢?如果发现监视索引查找和维护哈希索引结构的额外 开销远远超过了自适应哈希索引带来的性能提升就需要关闭这个功能。
同时在 MySQL 5.7 中,自适应哈希索引搜索系统被分区。每个索引都绑定到 一个特定的分区,每个分区都由一个单独的 latch 锁保护。分区由 innodb_adaptive_hash_index_parts 配置选项控制 。在早期版本中,自适应哈 希索引搜索系统受到单个 latch 锁的保护,这可能成为繁重工作负载下的争用 点。innodb_adaptive_hash_index_parts 默认情况下,该 选项设置为 8。最大 设置为 512。
全文检索之倒排索引
什么是全文检索(Full-Text Search)?它是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获得全文中有关章、 节、段、句、词等信息,也可以进行各种统计和分析。我们比较熟知的 Elasticsearch、 Solr 等就是全文检索引擎,底层都是基于 Apache Lucene 的。
举个例子,现在我们要保存唐宋诗词,数据库中我们们会怎么设计?诗词表 我们可能的设计如下:
朝代 | 作者 | 年代 | 标题 | 全文 |
---|---|---|---|---|
唐 | 李白 | 静夜思 | 床前明月光,疑是地上霜。 举头望明月,低头思故乡。 | |
宋 | 李清照 | 如梦令 | 常记溪亭日暮,沉醉不知归路,兴尽晚回 舟,误入藕花深处。争渡,争渡,惊起一 滩鸥鹭。 |
要根据朝代或者作者寻找诗,都很简单,比如“select 诗词全文 from 诗词表 where 作者=‘李白’”,如果数据很多,查询速度很慢,怎么办?我们可以在 对应的查询字段上建立索引加速查询。
但是如果我们现在有个需求:要求找到包含“望”字的诗词怎么办?用 “select 诗词全文 from 诗词表 where 诗词全文 like‘%望%’”,这个意味着 要扫描库中的诗词全文字段,逐条比对,找出所有包含关键词“望”字的记录,。 基本上,数据库中一般的 SQL 优化手段都是用不上的。数量少,大概性能还能接 受,如果数据量稍微大点,就完全无法接受了,更何况在互联网这种海量数据的 情况下呢?怎么解决这个问题呢,用倒排索引。
比如现在有:
*蜀道难(唐)李白 蜀道之难难于上青天,侧身西望长咨嗟。*静夜思(唐)李白 举头望明月,低头思故乡。
春台望(唐)李隆基 暇景属三春,高台聊四望。
鹤冲天*(宋)*柳永 黄金榜上,偶失龙头(领头)(领头)望。明代暂遗贤,如何向?未遂风云便, 争不恣狂荡。何须论得丧?才子词人,自是白衣卿相。烟花巷陌,依约丹青屏障。 幸有意中人,堪寻访。且恁偎红翠,风流事,平生畅。青春都一饷。忍把浮名, 换了浅斟低唱!
都有望/上字,于是我们可以这么保存
序号 | 关键字 | 蜀道难 | 静夜思 | 春台望 | 鹤冲天 |
---|---|---|---|---|---|
1 | 望 | 有 | 有 | 有 | 有 |
2 | 上 | 有 | 有 |
其实,上述诗词的中每个字都可以作为关键字,然后建立关键字和文档之间 的对应关系,也就是标识关键字被哪些文档包含。(正常是文档中找词, 更具词找文档,所以叫倒排索引)
所以,倒排索引就是,将文档中包含的关键字全部提取处理,然后再将关键 字和文档之间的对应关系保存起来,最后再对关键字本身做索引排序。用户在检 索某一个关键字是,先对关键字的索引进行查找,再通过关键字与文档的对应关 系找到所在文档。
在存储在关系型数据库中的数据,需要我们事先分析将数据拆分为不同的字 段,而在 es 这类的存储中,需要应用程序根据规则自动提取关键字,并形成对 应关系。
这些预先提取的关键字,在全文检索领域一般被称为 term(词项),文档 的词项提取在 es 中被称为文档分析,这是全文检索很核心的过程,必须要区分 哪些是词项,哪些不是,比如很多场景下,apple 和 apples 是同一个东西,望和看其实是同一个动作
从 InnoDB 1.2.x 版本开始,InnoDB 存储引擎开始支持全文检索,对应的 MySQL 版本是 5.6.x 系列。不过 MySQL 从设计之初就是关系型数据库,存储引擎 虽然支持全文检索,整体架构上对全文检索支持并不好而且限制很多,比如每张 表只能有一个全文检索的索引,不支持没有单词界定符( delimiter)的语言, 如中文、日语、韩语等。(空格)
所以如果有大批量或者专门的全文检索需求,还是应该选择专门的全文检索 引擎,毕竟 Elastic 靠着全文检索起家,然后产品化、公司化后依赖全文检索不断 扩充产品线和应用场景,并推出商业版本的解决方案然后融资上市,现在的市值 已达 100 亿美元(2021/03/24-纽约证券交易所中的市值 99.84 亿美元)。
具体如何使用 InnoDB 存储引擎的全文检索,请自行查阅相关官方文档或者书籍
Elastic 发家小故事
多年前,一个叫做 Shay Banon 的刚结婚不久的失业开发者,由于妻子要去 伦敦学习厨师,他便跟着也去了。在他找工作的过程中,为了给妻子构建一个食 谱的搜索引擎,他开始构建一个早期版本的 Lucene。
直接基于 Lucene 工作会比较困难,所以 Shay 开始抽象 Lucene 代码以便 Java 程序员可以在应用中添加搜索功能。他发布了他的第一个开源项目,叫做 “ Compass”。
后来 Shay 找到一份工作,这份工作处在高性能和内存数据网格的分布式环 境中,因此高性能的、实时的、分布式的搜索引擎也是理所当然需要的。然后他 决定重写 Compass 库使其成为一个独立的服务叫做 Elasticsearch。
第一个公开版本出现在 2010 年 2 月,在那之后 Elasticsearch 已经成为 Github 上最受欢迎的项目之一,代码贡献者超过 300 人。一家主营
Elasticsearch 的公司就此成立,他们一边提供商业支持一边开发新功能,不过Elasticsearch 将永远开源且对所有人可用
深入思考索引在查询中的使用
索引在查询中的作用到底是什么?在我们的查询中发挥着什么样的作用 呢?
1、一个索引就是一个 B 树,索引让我们的查询可以快速定位和扫描到我们 需要的数据记录上,加快查询的速度。
2、一个 select 查询语句在执行过程中一般最多能使用一个二级索引,即使在 where 条件中用了多个二级索引。
扫描区间
对于某个查询来说,最简单粗暴的执行方案就是扫描表中的所有记录,判断 每一条记录是否符合搜索条件。如果符合,就将其发送到客户端,否则就跳过该 记录。这就是全表扫描。
对于使用 InnoDB 存储引擎的表来说,全表扫描意味着从聚簇索引第一个叶 子节点的第一条记录开始,沿着记录所在的单向链表向后扫描,直到最后一个叶 子节点的最后一条记录。虽然全表扫描是一种很笨的执行方案,但却是一种万能 的执行方案,所有的查询都可以使用这种方案来执行,只是效率不高。
我们有了索引,利用 B 树查找索引列值等于某个值的记录,这样可以明显 减少需要扫描的记录数量。由于 B 树叶子节点中的记录是按照索引列值由小到 大的顺序排序的,所以即使只扫描某个区间或者某些区间中的记录也可以明显减 少需要扫描的记录数量。比如下面这个查询语句:
SELECT * FROM order_exp WHERE id >= 3 AND id<= 99;
这个语句其实是想查找 id 值在[3,99]区间中的所有聚簇索引记录。我们可以 通过聚簇索引对应的 B 树快速地定位到 id 值为 3 的那条聚簇索引记录,然后沿着记录所在的单向链表向后扫描,直到某条聚簇索引记录的 id 值不在[3,99]区间 中为止。
与全表扫描相比,扫描 id 值在[3,99]区间中的记录已经很大程度地减少了需 要扫描的记录数量,所以提升了查询效率。其实所谓的全表扫描,我们可以理解 为扫描的区间是[负无穷,正无穷]或者[第一条记录,最后一条记录]。
再看下面这个查询语句:
SELECT * FROM order_exp WHERE id in(3,9) OR (id>=23 AND id<= 99);
这里有几个扫描区间?三个,两个单独扫描区间[3,3]、[9,9],一个范围扫描 区间[23,99]
再看下面这个查询语句:
SELECT * FROM order_exp WHERE order_no <‘DD00_10S’ AND expire_time> ‘2021-03-22 18:28:28’ AND order_note > ‘7 排’;
这个语句里,order_no 和 expire_time 都有索引,order_note 没有索引,那 会有两个扫描区间吗?并不会,请记住,一个 Select 查询语句在执行过程中一般 最多能使用一个二级索引。那么也就是说:
如果用 idx_order_no 执行查询,那扫描区间就是[第一条记录,‘DD00_10S’], expire_time> ‘2021-03-22 18:28:28’ AND order_note > '7 排’只能成为普通的搜索或 者说判定条件。
如果说用 idx_expire_time 执行查询,那扫描区间就是[‘2021-03-22 18:28:28’, 最后一条记录],order_no <‘DD00_10S’ AND order_note > '7 排’只能成为普通的搜 索或者说判定条件。
无论用哪个索引执行查询,都需要获取到索引中的记录后,进行回表,获取 到完整的用户记录后再根据判定条件判断这条记录是否满足 SQL 语句的要求。
范围区间扫描
其实对于 B 树索引来说,只要索引列和常数使用=、<=>、IN、NOT IN、IS NULL、 IS NOT NULL、>、<、>=、<=、BETWEEN、!=(不等于也可以写成<>)或者 LIKE 操作符连接起来,就可以产生若干个区间
1、IN 操作符的效果和若干个等值匹配操作符=
之间用OR
连接起来是一样 的,也就是说会产生多个单点区间,比如下边这两个语句的效果是一样的:
SELECT * FROM order_exp WHERE insert_time IN (2021-03-22 18:23:42, yyyy);
SELECT * FROM order_exp WHERE insert_time= 2021-03-22 18:23:42 OR insert_time = yyyy;
2、!=产生的扫描区间呢?比如
SELECT * FROM order_exp WHERE order_no != ‘DD00_9S’
此时使用 idx_expire_time 执行查询时对应的扫描区间就是[第一条记录 , ‘DD00_9S’]和[ ‘DD00_9S’,最后一条记录]。
3、LIKE 操作符比较特殊,只有在匹配完整的字符串或者匹配字符串前缀时 才产生合适的扫描区间。
对于某个索引列来说,字符串前缀相同的记录在由记录组成的单向链表中肯 定是相邻的。比如我们有一个搜索条件是 note LIKE’ b%’,对于二级索引 idx_note 来说,所有字符串前缀为’b’的二级索引记录肯定是相邻的。这也就意味着我们只 要定位到 idx_note 值的字符串前缀为’b’的第一条记录,就可以沿着记录所在的单 向链表向后扫描,直到某条二级索引记录的字符串前缀不为 a 为止。
很显然,note LIKE’ b%’ 形成的扫描区间相当于[‘b’, ‘c’)。
不过在日常的工作中,一个查询的 WHERE 子句可能有很多个小的搜索条件, 这些搜索条件需要使用 AND 或者 OR 操作符连接起来,我们来看看怎么从由 AND 或 OR 组成的复杂搜索条件中提取出正确的范围区间。
所有搜索条件都可以使用某个索引的情况
show create table order_exp;
CREATE TABLE `order_exp` (
`id` bigint NOT NULL AUTO_INCREMENT COMMENT '订单的主键',
`order_no` varchar(50) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '订单的编号',
`order_note` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '订单的说明',
`insert_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '插入订单的时间',
`expire_duration` bigint NOT NULL COMMENT '订单的过期时长,单位秒',
`expire_time` datetime NOT NULL COMMENT '订单的过期时间',
`order_status` smallint NOT NULL DEFAULT '0' COMMENT '订单的状态,0:未支付;1:已支付;-1:已过期,关闭',
PRIMARY KEY (`id`) USING BTREE,
UNIQUE KEY `u_idx_day_status` (`insert_time`,`order_status`,`expire_time`) USING BTREE,
KEY `idx_order_no` (`order_no`) USING BTREE,
KEY `idx_expire_time` (`expire_time`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=10819 DEFAULT CHARSET=utf8mb3 ROW_FORMAT=DYNAMIC
有时候每个搜索条件都可以使用到某个索引,比如下边这个查询语句:
SELECT * FROM order_exp WHERE order_no > 'DD00_6S' AND order_no > 'DD00_9S';
## 已知索引 idx_order_no
这个查询中的搜索条件都可以使用到 idx_order_no,也就是说每个搜索条件 都对应着一个 idx_order_no 的范围区间。这两个小的搜索条件使用 AND 连接起 来,也就是要取两个范围区间的交集,两者交集当然就是 order_no > ‘DD00_9S’ 了,也就是说上边这个查询使用 idx_order_no 的范围区间就是(‘DD00_9S’, 最后 一条记录)。
再看一下使用 OR 将多个搜索条件连接在一起的情况:
SELECT * FROM order_exp WHERE order_no > 'DD00_6S' OR order_no > 'DD00_9S';
OR 意味着需要取各个范围区间的并集,所以上边这个查询使用 idx_expire_time 的范围区间就是( ‘DD00_6S’ ,最后一条记录)
有的搜索条件无法使用索引的情况
比如下边这个查询:
SELECT * FROM order_exp WHERE expire_time> '2021-03-22 18:35:09' AND order_note = 'abc';
## 已知索引 idx_expire_time
这个查询语句中能利用的索引只有 idx_expire_time 一个,而 idx_expire_time 这个二级索引的记录中又不包含 order_note 这个字段,所以在使 用二级索引 idx_expire_time 定位记录的阶段用不到 order_note = 'abc’这个条件,这个条件是在回表获取了完整的用户记录后才使用的,而范围区间是为了到索引 中取记录中提出的概念,所以在确定范围区间的时候不需要考虑 order_note = 'abc’这个条件。
我们把上边的查询中用不到 idx_expire_time 的搜索条件化简之后就是这样
SELECT * FROM order_exp WHERE expire_time> '2021-03-22 18:35:09';
也就是说最上边那个查询使用 idx_expire_time 的范围区间就是:(‘2021-03-22 18:35:09’,最后一条记录)。
再来看一下使用 OR 的情况:
SELECT * FROM order_exp WHERE expire_time> '2021-03-22 18:35:09' OR order_note = 'abc';
这条语句在搜索时可以化简为:
SELECT * FROM order_exp ; # or 使得索引失效了
这也就说如果我们使用 idx_expire_time 执行查询的话,对应的范围区间就是 [第一条记录,最后一条记录],也就是需要将全部二级索引的记录进行回表,这个 代价肯定比直接全表扫描都大了。也就是说一个使用到索引的搜索条件和没有使 用该索引的搜索条件使用 OR 连接起来后是无法使用该索引的。为什么?道理很 简单,idx_expire_time 这个二级索引的记录中不包含 order_note 这个字段,那就 说,即使二级索引 idx_expire_time 中找到了满足 expire_time> '2021-03-22 18:35:09’的记录,是无法判定 order_note 是否满足 order_note = 'abc’的,又因 为是 OR 条件,所以必须要在主键索引中从第一条记录到最后一条记录逐条判定 order_note 是否等于 ‘abc’。
复杂搜索条件下找出范围匹配的区间
有的查询的搜索条件可能特别复杂,比方说下边这个:
SELECT * FROM order_exp
WHERE
(order_no > 'DD00_9S' AND expire_time = '2021-03-22 18:35:09' ) OR
(order_no < 'DD00_6S' AND order_no > 'DD00_9S') OR
(order_no LIKE '%0S' AND order_no > 'DD00_12S' AND
(expire_time < '2021-03-22 18:28:28' OR order_note = 'abc'));
## 已知索引 idx_列名
idx_order_no
idx_expire_time
分析一下:
首先查看 WHERE 子句中的搜索条件都涉及到了哪些列,哪些列可能使用到 索引。
这个查询的搜索条件涉及到了 order_no、expire_time、order_note 这 3 个列, 然后 order_no 列有二级索引 idx_order_no,expire_time 列有二级索引 idx_expire_time。
对于那些可能用到的索引,分析它们的范围区间。
使用 idx_order_no 执行查询
我们需要把那些用不到该索引的搜索条件暂时移除掉。上边的查询中除了有 expire_time 和 order_note 列不能使用到 idx_order_no 索引外,order_no LIKE '%0S’也使用不到索引。
如果条件太复杂,看着演化怕出错,我们可以把所有用不到的搜索条件视为 True 来进行中间替换,所以把这些搜索条件替换为 True 之后的样子就是这样:
SELECT * FROM order_exp
WHERE
(order_no > 'DD00_9S' AND true) OR
(order_no < 'DD00_6S' AND order_no > 'DD00_9S') OR
(true AND order_no > 'DD00_12S' AND
(true OR true));
再简化一次
SELECT * FROM order_exp
WHERE
(order_no > 'DD00_9S') OR
(order_no < 'DD00_6S' AND order_no > 'DD00_9S') OR
(order_no > 'DD00_12S');
接下来替换掉永远为 TRUE 或 FALSE 的条件
因为符合 order_no < ‘DD00_6S’ AND order_no > 'DD00_9S’永远为 FALSE,所以 上边的搜索条件可以被写成这样:
SELECT * FROM order_exp
WHERE
(order_no > 'DD00_9S') OR
(order_no > 'DD00_12S');
## 再化简 注意: DD00_12S 和 DD00_9S 按文本索引排序1在9之前
SELECT * FROM order_exp
WHERE
(order_no > 'DD00_12S')
上边那个复杂搜索 条件的查询语句如果使用 idx_order_no 索引执行查询的话,需要把满足 order_no > 'DD00_12S’的二级索引记录都取出来,然后拿着这些记录的 id 再进行 回表,得到完整的用户记录之后再使用其他的搜索条件进行过滤。记住,我们说 的是如果使用 idx_order_no 索引执行查询,不代表 MySQL 一定会使用,因为 MySQL 需要做整体评估,才能确定是否使用这个索引还是别的索引,或者是干脆 全表扫描。
使用 idx_expire_time 执行查询
我们需要把那些用不到该索引的搜索条件暂时使用 TRUE 条件替换掉,其中 有关 order_no 和 order_note 的搜索条件都需要被替换掉,替换结果就是
SELECT * FROM order_exp
WHERE
(true AND expire_time = '2021-03-22 18:35:09' ) OR
(true) OR
(true AND
(expire_time < '2021-03-22 18:28:28' OR true));
## 布尔运算再化简
(true AND expire_time = '2021-03-22 18:35:09' )
## 在化简
true
Tips: 假设上面这个 SQL 语句,执行全表扫描的代价大概是 2169,用 idx_order_no 索引的代价大概是 6211,所以,实际执行的时候,MySQL 会选择全表扫描。至 于代价怎么算来的,我们后面会学到 |
使用联合索引执行查询时对应的扫描区间
show create table order_exp;
CREATE TABLE `order_exp` (
`id` bigint NOT NULL AUTO_INCREMENT COMMENT '订单的主键',
`order_no` varchar(50) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '订单的编号',
`order_note` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '订单的说明',
`insert_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '插入订单的时间',
`expire_duration` bigint NOT NULL COMMENT '订单的过期时长,单位秒',
`expire_time` datetime NOT NULL COMMENT '订单的过期时间',
`order_status` smallint NOT NULL DEFAULT '0' COMMENT '订单的状态,0:未支付;1:已支付;-1:已过期,关闭',
PRIMARY KEY (`id`) USING BTREE,
UNIQUE KEY `u_idx_day_status` (`insert_time`,`order_status`,`expire_time`) USING BTREE,
KEY `idx_order_no` (`order_no`) USING BTREE,
KEY `idx_expire_time` (`expire_time`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=10819 DEFAULT CHARSET=utf8mb3 ROW_FORMAT=DYNAMIC
联合索引的索引列包含多个列,B 树每一层页面以及每个页面中的记录采用 的排序规则较为复杂,以 order_exp 表的 u_idx_day_status 联合索引为例,它采 用的排序规则如下所示:
先按照 insert_time 列的值进行排序。
在 insert_time 列的值相同的情况下,再按照 order_status 列的值进行排序。
在 insert_time 和 order_status 列的值都相同的情况下,再按照 expire_time 列的值进行排序。
对于下边这个查询 Q1 来说:
Q1:SELECT * FROM order_exp WHERE insert_time = ‘2021-03-22 18:34:55’;
由于二级索引记录是先按照 insert_time 列的值进行排序的,所以所有符合 insert_time = '2021-03-22 18:34:55’条件的记录肯定是相邻的,我们可以定位到第 一条符合 insert_time = '2021-03-22 18:34:55’条件的记录,然后沿着记录所在的单 向链表向后扫描,直到某条记录不符合 insert_time = '2021-03-22 18:34:55’条件为 止(当然,对于获取到的每一条二级索引记录都要执行回表操作)。(如果是唯一索引就不需要对等值做扫描了)
也就是说,如果我们使用 u_idx_day_status 索引执行查询 Q1 时,对应的扫 描区间就是[‘2021-03-22 18:34:55’, ‘2021-03-22 18:34:55’],形成这个扫描区间的条 件就是 insert_time = ‘2021-03-22 18:34:55’。
对于下边这个查询 Q2 来说:
Q2:SELECT * FROM order_exp WHERE insert_time = ‘2021-03-22 18:34:55’ AND order_status = 0;
由于二级索引记录是先按照 insert_time 列的值进行排序的;在 insert_time 列的值相等的情况下,再按照 order_status 列进行排序。所以符合 insert_time = ‘2021-03-22 18:34:55’ AND order_status = 0 条件的二级索引记录肯定是相邻的, 我们可以定位到第一条符合 insert_time=‘2021-03-22 18:34:55’ AND order_status=0 条件的记录,然后沿着记录所在的链表向后扫描,直到某条记录 不符合 insert_time='2021-03-22 18:34:55’条件或者 order_status=0 条件为止。
也就是说,如果我们使用 u_idx_day_status 索引执行查询 Q2 时,可以形成 扫描区间[(‘2021-03-22 18:34:55’, 0), (‘2021-03-22 18:34:55’, 0)],形成这个扫描区间 的条件就是 insert_time = ‘2021-03-22 18:34:55’ AND order_status = 0。
对于下边这个查询 Q3 来说:
Q3:SELECT * FROM order_exp WHERE insert_time = ‘2021-03-22 18:34:55’ AND order_status = 0 AND expire_time = ‘2021-03-22 18:35:13’;
由于二级索引记录是先按照 insert_time 列的值进行排序的;在 insert_time 列的值相等的情况下,再按照 order_status 列进行排序;在 insert_time 和 order_status 列的值都相等的情况下,再按照 expire_time 列进行排序。所以符合 insert_time = ‘2021-03-22 18:34:55’ AND order_status = 0 AND expire_time = '2021-03-22 18:35:13’条件的二级索引记录肯定是相邻的,我们可以定位到第一条 符合 insert_time=‘2021-03-22 18:34:55’ AND order_status=0 AND expire_time='2021-03-22 18:35:13’条件的记录,然后沿着记录所在的链表向后扫 描,直到某条记录不符合 insert_time='2021-03-22 18:34:55’条件或者 order_status=0 条件或者 expire_time='2021-03-22 18:35:13’条件为止。如果我们使 用 u_idx_day_status 索引执行查询 Q3 时,可以形成扫描区间[(‘2021-03-22 18:34:55’, 0, ‘2021-03-22 18:35:13’), (‘2021-03-22 18:34:55’, 0, ‘2021-03-22 18:35:13’)],形成这个扫描区间的条件就是 insert_time = ‘2021-03-22 18:34:55’ AND order_status = 0 AND expire_time = ‘2021-03-22 18:35:13’。
对于下边这个查询 Q4 来说:
Q4:SELECT * FROM order_exp WHERE insert_time < ‘2021-03-22 18:34:55’;
由于二级索引记录是先按照 insert_time 列的值进行排序的,所以所有符合 insert_time < '2021-03-22 18:34:55’条件的记录肯定是相邻的,我们可以定位到第 一条符合 insert_time < '2021-03-22 18:34:55’条件的记录(其实就是 u_idx_day_status 索引第一个叶子节点的第一条记录),然后沿着记录所在的链表 向前扫描,直到某条记录不符合 insert_time < '2021-03-22 18:34:55’为止。
对于下边这个查询 Q5 来说:
Q5:SELECT * FROM order_exp WHERE insert_time = ‘2021-03-22 18:34:55’ AND order_status > =0 ;
由于二级索引记录是先按照 insert_time 列的值进行排序的;在 insert_time 列的值相等的情况下,再按照 order_status 列进行排序。也就是说在符合 insert_time = '2021-03-22 18:34:55’条件的二级索引记录中,是按照 order_status 列的值进行排序的,那么此时符合 insert_time = ‘2021-03-22 18:34:55’ AND order_status > =0 ;条件的二级索引记录肯定是相邻的。我们可以定位到第一条符 合 insert_time = ‘2021-03-22 18:34:55’ AND order_status > =0 ;条件的记录,然后沿 着记录所在的链表向后扫描,直到某条记录不符合 insert_time='2021-03-22 18:34:55’条件或者 order_status > =0 条件为止。
也就是说,如果我们使用 u_idx_day_status 索引执行查询 Q5 时,可以形成 扫描区间,条件就是 insert_time = ‘2021-03-22 18:34:55’ AND order_status > =0 ;。
对于下边这个查询 Q6 来说:
Q6:SELECT * FROM order_exp WHERE order_status = 1;
由于二级索引记录不是直接按照 order_status 列的值排序的,所以符合 order_status = 1 的二级索引记录可能并不相邻,也就意味着我们不能通过这个
order_status = 1 搜索条件来减少需要扫描的记录数量。在这种情况下,我们是不 会使用 u_idx_day_status 索引执行查询的。
对于下边这个查询 Q7 来说:
Q7:SELECT * FROM order_exp WHERE insert_time = ‘2021-03-22 18:34:55’ AND expire_time = ‘2021-03-22 18:35:12’;
由于二级索引记录是先按照 insert_time 列的值进行排序的,所以符合 insert_time = '2021-03-22 18:34:55’条件的二级索引记录肯定是相邻的,但是对于 符合 insert_time = '2021-03-22 18:34:55’条件的二级索引记录来说,并不是直接按 照 expire_time 列进行排序的,也就是说我们不能根据搜索条件 expire_time = '2021-03-22 18:35:12’来进一步减少需要扫描的记录数量。那么如果我们使用 u_idx_day_status 索引执行查询的话,可以定位到第一条符合 insert_time='2021-03-22 18:34:55’条件的记录,然后沿着记录所在的单向链表向后 扫描,直到某条记录不符合 insert_time = '2021-03-22 18:34:55’条件为止。所以在 使用 u_idx_day_status 索引执行查询 Q7 的过程中,对应的扫描区间其实是 [‘2021-03-22 18:34:55’, ‘2021-03-22 18:34:55’],形成该扫描区间的搜索条件是 insert_time = ‘2021-03-22 18:34:55’,与 expire_time = '2021-03-22 18:35:12’无关。(但是expire_time 可以作为索引下推的条件)
对于下边这个查询 Q8 来说:
Q8:SELECT * FROM order_exp WHERE insert_time < ‘2021-03-22 18:34:57’ AND order_status = 1;
由于二级索引记录是先按照 insert_time 列的值进行排序的,所以符合 insert_time < '2021-03-22 18:34:57’条件的二级索引记录肯定是相邻的,但是对于 符合 insert_time < '2021-03-22 18:34:57’条件的二级索引记录来说,并不是直接按 照 order_status 列进行排序的,也就是说我们不能根据搜索条件 order_status = 0 来进一步减少需要扫描的记录数量。那么如果我们使用 u_idx_day_status 索引执 行查询的话,可以定位到第一条符合 insert_time 的记录,其实就是 u_idx_day_status 索引第一个叶子节点的第一条记录,所以在使用 u_idx_day_status 索引执行查询 Q8 的过程中,对应的扫描区间其实是[第一条记 录, ‘2021-03-22 18:34:57’)。(但是order_status 可以作为索引下推的条件)
简单了解 MyISAM 中的索引
至此,我们介绍的都是 InnoDB 存储引擎中的索引方案,下面再简单介绍一下 MyISAM 存储引擎中的索引方案。我们知道 InnoDB 中索引即数据,也就是聚簇索 引的那棵 B 树的叶子节点中已经把所有完整的用户记录都包含了,而 MyISAM 的 索引方案虽然也使用树形结构,但是却将索引和数据分开存储的。
MyISAM 将表中的记录按照记录的插入顺序单独存储在一个文件中,称之为 数据文件。这个文件并不划分为若干个数据页,有多少记录就往这个文件中塞多 少记录就成了。我们可以通过行号而快速访问到一条记录。
由于在插入数据的时候并没有刻意按照主键大小排序,所以我们并不能在这 些数据上使用二分法进行查找。
使用 MyISAM 存储引擎的表会把索引信息另外存储到一个称为索引文件的另 一个文件中。MyISAM 会单独为表的主键创建一个索引,只不过在索引的叶子节 点中存储的不是完整的用户记录,而是主键值+行号的组合。也就是先通过索引 找到对应的行号,再通过行号去找对应的记录!(行号就相当于聚簇索引的主键, MyISAM除了全表扫描,都需要回表)
这一点和 InnoDB 是完全不相同的,在 InnoDB 存储引擎中,我们只需要根据 主键值对聚簇索引进行一次查找就能找到对应的记录,而在 MyISAM 中却需要进 行一次回表操作,意味着 MyISAM 中建立的索引相当于全部都是二级索引!
如果有需要的话,我们也可以对其它的列分别建立索引或者建立联合索引, 原理和 InnoDB 中的索引差不多,不过在叶子节点处存储的是相应的列+行号。 这些索引也全部都是二级索引。
创建和删除索引的语句
那我们如何使用 SQL 语句去建立这种索引呢? InnoDB 和 MyISAM 会自动为主 键或者声明为 UNIQUE 的列去自动建立 B 树索引,但是如果我们想为其他的列 建立索引就需要我们显式的去指明。为啥不自动为每个列都建立个索引呢?我们 待会说。
查看索引
show index from tablename \G
创建修改索引
-- 1. 建表时创建 [key|index]
create table tablename (
列信息
[key|index] 索引名 (需要被应用的单个列或多个列)
)
-- 2. 单独创建 create [unique] index
create [unique] index indexName on tableName(columnName(length));
-- 3. 通过修改表创建 add
alter table tableName add [unique] index [indexName] on (columnName(length))
删除索引
drop index [indexName] on tableName;
alter table tableName drop [key|index] IndexName;
索引的代价
世界上从来没有只有好处没有坏处的东西,如果你有,请你一定要告诉我, 让我也感受一下。虽然索引是个好东西,在学习如何更好的使用索引之前先要了 解一下使用它的代价,它在空间和时间上都会拖后腿。
空间上的代价
这个是显而易见的,每建立一个索引都要为它建立一棵 B 树,每一棵 B 树 的每一个节点都是一个数据页,一个页默认会占用 16KB 的存储空间,一棵很大 的 B 树由许多数据页组成会占据很多的存储空间。
时间上的代价
每次对表中的数据进行增、删、改操作时,都需要去修改各个 B 树索引。 而且我们讲过,B 树每层节点都是按照索引列的值从小到大的顺序排序而组成了 双向链表。不论是叶子节点中的记录,还是非叶子内节点中的记录都是按照索引 列的值从小到大的顺序而形成了一个单向链表。
而增、删、改操作可能会对节点和记录的排序造成破坏,所以存储引擎需要 额外的时间进行一些记录移位,页面分裂、页面回收的操作来维护好节点和记录 的排序。如果我们建了许多索引,每个索引对应的 B 树都要进行相关的维护操 作,这必然会对性能造成影响。
既然索引这么有用,我们是不是创建越多越好?既然索引有代价,我们还是 别创建了吧?当然不是!那么我们应该怎么创建索引呢?
高性能的索引创建策略
正确地创建和使用索引是实现高性能查询的基础。前面我们已经了解了索引 相关的数据结构,各种类型的索引及其对应的优缺点。现在我们一起来看看如何 真正地发挥这些索引的优势。
索引列的类型尽量小
我们在定义表结构的时候要显式的指定列的类型,以整数类型为例,有 TTNYINT、NEDUMNT、INT、BIGTNT 这么几种,它们占用的存储空间依次递增, 我们这里所说的类型大小指的就是该类型表示的数据范围的大小。能表示的整数 范围当然也是依次递增,如果我们想要对某个整数列建立索引的话,在表示的整 数范围允许的情况下,尽量让索引列使用较小的类型,比如我们能使用 INT 就不 要使用 BIGINT,能使用 NEDIUMINT 就不要使用 INT,这是因为:
- 数据类型越小,在查询时进行的比较操作越快(CPU 层次)
- ·数据类型越小,索引占用的存储空间就越少,在一个数据页内就可以放下 更多的记录,从而减少磁盘I/O 带来的性能损耗,也就意味着可以把更多的数据 页缓存在内存中,从而加快读写效率。
这个建议对于表的主键来说更加适用,因为不仅是聚簇索引中会存储主键值, 其他所有的二级索引的节点处都会存储一份记录的主键值,如果主键适用更小的 数据类型,也就意味着节省更多的存储空间和更高效的 I/O。
索引选择性和前缀索引
索引的选择性/离散性
创建索引应该选择选择性/离散性高的列。索引的选择性/离散性是指,不重 复的索引值(也称为基数,cardinality)和数据表的记录总数(N)的比值,范围从 1/N 到 1 之间。索引的选择性越高则查询效率越高,因为选择性高的索引可以让 MySQL 在查找时过滤掉更多的行。唯一索引的选择性是 1,这是最好的索引选择 性,性能也是最好的。
很差的索引选择性就是列中的数据重复度很高,比如性别字段,不考虑政治 正确的情况下,只有两者可能,男或女。那么我们在查询时,即使使用这个索引, 从概率的角度来说,依然可能查出一半的数据出来。
怎么算索引的选择性/离散性?比如 order_exp 这个表:
select COUNT(DISTINCT order_no)/count(*) cnt from order_exp;
mysql> select COUNT(DISTINCT order_no)/count(*) cnt from order_exp;
--------
| cnt |
--------
| 0.9676 |
--------
1 row in set (0.18 sec)
mysql> select COUNT(DISTINCT order_status)/count(*) cnt from order_exp;
--------
| cnt |
--------
| 0.0001 |
--------
1 row in set (0.11 sec)
很明显,order_no 列上的索引就比 order_status 列上的索引的选择性就要好,原 因很简单,因为 order_status 列中的值只有-1,0,1 三种。
前缀索引
有时候需要索引很长的字符列,这会让索引变得大且慢。一个策略是前面提 到过的模拟哈希索引。
模拟哈希索引:
order_exp 表中 order_note 字段很长,想把它作为一个索引,我们可以增加 一个 order_not_hash 字段来存储 order_note 的哈希值,然后在 order_not_hash 上 建立索引,相对于之前的索引速度会有明显提升,一个是对完整的 order_note 做索引,而后者则是用整数哈希值做索引,显然数字的比较比字符串的匹配要高 效得多。
但是缺陷也很明显:
1、需要额外维护 order_not_hash 字段;
2、哈希算法的选择决定了哈希冲突的概率,不良的哈希算法会导致重复值 很多;
3、不支持范围查找。
还可以做些什么改进呢?还可以索引开始的部分字符,这样可以大大节约索 引空间,从而提高索引效率。但这样也会降低索引的选择性。一般情况下我们需 要保证某个列前缀的选择性也是足够高的,以满足查询性能。(尤其对于 BLOB、 TEXT 或者很长的 VARCHAR 类型的列,应该使用前缀索引,因为 MySQL 不允许索 引这些列的完整长度)。
诀窍在于要选择足够长的前缀以保证较高的选择性,同时又不能太长(以便 节约空间)。前缀应该足够长,以使得前缀索引的选择性接近于索引整个列。换 句话说,前缀的“基数”应该接近于完整列的“基数”。
为了决定前缀的合适长度,可以找到最常见的值的列表,然后和最常见的前 缀列表进行比较。
首先找到最常见的值的列表:
SELECT COUNT(*) AS cnt,order_note FROM order_exp GROUP BY order_note ORDER BY cnt DESC LIMIT 20;
mysql> SELECT COUNT(*) AS cnt,order_note FROM order_exp GROUP BY order_note ORDER BY cnt DESC LIMIT 20;
----- -----------------------------------------
| cnt | order_note |
----- -----------------------------------------
| 24 | 你好,李焕英。7排23号,过期时长:DD00_23S |
| 24 | 你好,李焕英。7排17号,过期时长:DD00_17S |
| 23 | 你好,李焕英。7排24号,过期时长:DD00_24S |
| 22 | 你好,李焕英。7排10号,过期时长:DD00_10S |
| 22 | 你好,李焕英。7排7号,过期时长:DD00_7S |
| 20 | 你好,李焕英。7排5号,过期时长:DD00_5S |
| 19 | 你好,李焕英。7排6号,过期时长:DD00_6S |
| 19 | 你好,李焕英。7排14号,过期时长:DD00_14S |
| 19 | 你好,李焕英。7排19号,过期时长:DD00_19S |
| 17 | 你好,李焕英。7排16号,过期时长:DD00_16S |
| 17 | 你好,李焕英。7排18号,过期时长:DD00_18S |
| 17 | 你好,李焕英。7排9号,过期时长:DD00_9S |
| 16 | 你好,李焕英。7排12号,过期时长:DD00_12S |
| 16 | 你好,李焕英。7排13号,过期时长:DD00_13S |
| 16 | 你好,李焕英。7排21号,过期时长:DD00_21S |
| 15 | 你好,李焕英。7排15号,过期时长:DD00_15S |
| 15 | 你好,李焕英。7排22号,过期时长:DD00_22S |
| 15 | 你好,李焕英。7排8号,过期时长:DD00_8S |
| 13 | 你好,李焕英。7排11号,过期时长:DD00_11S |
| 13 | 你好,李焕英。7排20号,过期时长:DD00_20S |
----- -----------------------------------------
20 rows in set (0.47 sec)
通过观察数据的分布,我们可以大胆的猜测,前 9 个字符的选择性不会太好, 从第 10 个开始应该还不错。试一试:
SELECT
COUNT(DISTINCT LEFT(order_note,3))/COUNT(*) AS sel3,
COUNT(DISTINCT LEFT(order_note,4))/COUNT(*)AS sel4,
COUNT(DISTINCT LEFT(order_note,5))/COUNT(*) AS sel5,
COUNT(DISTINCT LEFT(order_note, 6))/COUNT(*) As sel6,
COUNT(DISTINCT LEFT(order_note, 7))/COUNT(*) As sel7,
COUNT(DISTINCT LEFT(order_note, 8))/COUNT(*) As sel8,
COUNT(DISTINCT LEFT(order_note, 9))/COUNT(*) As sel9,
COUNT(DISTINCT LEFT(order_note, 10))/COUNT(*) As sel10,
COUNT(DISTINCT LEFT(order_note, 11))/COUNT(*) As sel11,
COUNT(DISTINCT LEFT(order_note, 12))/COUNT(*) As sel12,
COUNT(DISTINCT LEFT(order_note, 13))/COUNT(*) As sel13,
COUNT(DISTINCT LEFT(order_note, 14))/COUNT(*) As sel14,
COUNT(DISTINCT LEFT(order_note, 15))/COUNT(*) As sel15,
COUNT(DISTINCT order_note)/COUNT(*) As total
FROM order_exp\G
*************************** 1. row ***************************
sel3: 0.0008
sel4: 0.0008
sel5: 0.0008
sel6: 0.0015
sel7: 0.0107
sel8: 0.0844
sel9: 0.1628
sel10: 0.3455
sel11: 0.4723
sel12: 0.6834
sel13: 0.8564
sel14: 0.9197
sel15: 0.9592
total: 0.9676
1 row in set (0.08 sec)
可以看见,从第 10 个开始选择性的增加值很高,随着前缀字符的越来越多, 选择度也在不断上升,但是增长到第 15 时,已经和第 14 没太大差别了,选择性 提升的幅度已经很小了,都非常接近整个列的选择性了。
那么针对这个字段做前缀索引的话,从第 13 到第 15 都是不错的选择,甚至 第 12 也不是不能考虑。当然不找到最常见的值的列表,直接计算前缀字符选择 性也是可以的。
在上面的示例中,已经找到了合适的前缀长度,如何创建前缀索引:
ALTER TABLE order_exp ADD KEY (order_note(14)); # 这字段长度对于字符串而言是很重要的,不等于全部就不是前缀索引了
建立前缀索引后查询语句并不需要更改:
select * from order_exp where order_note = 'xxxx';
前缀索引是一种能使索引更小、更快的有效办法,但另一方面也有其缺点 MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY,也无法使用前缀索引做覆 盖扫描。
有时候后缀索引 (suffix index)也有用途(例如,找到某个域名的所有电子邮 件地址)。MySQL 原生并不支持反向索引,但是可以把字符串反转后存储,并基 于此建立前缀索引。可以通过触发器或者应用程序自行处理来维护索引。
只为用于搜索、排序或分组的列创建索引
也就是说,只为出现在 WHERE 子句中的列、连接子句中的连接列创建索引, 而出现在查询列表中的列一般就没必要建立索引了,除非是需要使用覆盖索引; 又或者为出现在 ORDER BY 或 GROUP BY 子句中的列创建索引,这句话什么意思 呢?比如:
SELECT * FROM order_exp ORDER BY insert_time, order_status,expire_time;
查询的结果集需要先按照 insert_time 值排序,如果记录的 insert_time 值相 同,则需要按照 order_status 来排序,如果 order_status 的值相同,则需要按照 expire_time 排序。回顾一下联合索引的存储结构,u_idx_day_status 索引本身就 是按照上述规则排好序的,所以直接从索引中提取数据,然后进行回表操作取出 该索引中不包含的列就好了。
当然 ORDER BY 的子句后边的列的顺序也必须按照索引列的顺序给出,如果 给出 ORDER BY order_status,expire_time, insert_time 的顺序,那也是用不了 B 树 索引的,原因不用再说了吧。
explain SELECT * FROM order_exp ORDER BY insert_time, order_status,expire_time;
但是发现执行计划并没有使用索引
mysql> explain SELECT * FROM order_exp ORDER BY insert_time, order_status,expire_time\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: order_exp
partitions: NULL
type: ALL
possible_keys: NULL
key: NULL ##并没有使用索引
key_len: NULL
ref: NULL
rows: 10612
filtered: 100.00
Extra: Using filesort
1 row in set, 1 warning (0.00 sec)
## 再看看这个
mysql> explain SELECT order_status FROM order_exp ORDER BY insert_time, order_status,expire_time\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: order_exp
partitions: NULL
type: index
possible_keys: NULL
key: u_idx_day_status 使用了符合索引
key_len: 12
ref: NULL
rows: 10612
filtered: 100.00
Extra: Using index
1 row in set, 1 warning (0.00 sec)
### 说明在使用第一个sql时候,mysql引擎计算的全表扫描的成本比使用索引的成本更小一些
SELECT insert_time, order_status,expire_time,count(*) FROM order_exp GROUP BY insert_time, order_status,expire_time;
这个查询语句相当于做了 3 次分组操作:
先把记录按照 insert_time 值进行分组,所有 insert_time 值相同的记录划分 为一组。
将每个 insert_time 值相同的分组里的记录再按照 order_status 的值进行分组, 将 order_status 值相同的记录放到一个小分组里。
再将上一步中产生的小分组按照 expire_time 的值分成更小的分组。
然后针对最后的分组进行统计,如果没有索引的话,这个分组过程全部需要 在内存里实现,而如果有了索引的话,恰巧这个分组顺序又和我们的 u_idx_day_status 索引中的索引列的顺序是一致的,而我们的 B 树索引又是按照 索引列排好序的,这不正好么,所以可以直接使用 B 树索引进行分组。和使用 B 树索引进行排序是一个道理,分组列的顺序也需要和索引列的顺序一致。
多列索引
很多人对多列索引的理解都不够。一个常见的错误就是,为每个列创建独立 的索引,或者按照错误的顺序创建多列索引。
我们遇到的最容易引起困惑的问题就是索引列的顺序。正确的顺序依赖于使 用该索引的查询,并且同时需要考虑如何更好地满足排序和分组的需要。反复强 调过,在一个多列 B-Tree 索引中,索引列的顺序意味着索引首先按照最左列进 行排序,其次是第二列,等等。所以,索引可以按照升序或者降序进行扫描,以 满足精确符合列顺序的 ORDER BY、GROUP BY 和 DISTINCT 等子句的查询需求。
**所以多列索引的列顺序至关重要。**对于如何选择索引的列顺序有一个经验法 则:将选择性最高的列放到索引最前列。当不需要考虑排序和分组时,将选择性 最高的列放在前面通常是很好的。这时候索引的作用只是用于优化 WHERE 条件 的查找。在这种情况下,这样设计的索引确实能够最快地过滤出需要的行,对于 在 WHERE 子句中只使用了索引部分前缀列的查询来说选择性也更高。
然而,性能不只是依赖于索引列的选择性,也和查询条件的有关。可能需要 根据那些运行频率最高的查询来调整索引列的顺序,比如排序和分组,让这种情 况下索引的选择性最高。
同时,在优化性能的时候,可能需要使用相同的列但顺序不同的索引来满足 不同类型的查询需求。
设计三星索引
三星索引概念
对于一个查询而言,一个三星索引,可能是其最好的索引。
如果查询使用三星索引,一次查询通常只需要进行一次磁盘随机读以及一次 窄索引片的扫描,因此其相应时间通常比使用一个普通索引的响应时间少几个数 量级。
三星索引概念是在《Rrelational Database Index Design and the optimizers》 一 书中提出来的。原文如下:
The index earns one star if it places relevant rows adjacent to each other,
a second star if its rows are sorted in the order the query needs,
and a final star if it contains all the columns needed for the query.
-
索引将相关的记录放到一起则获得一星;(范围星)
-
如果索引中的数据顺序和查找中的排列顺序一致则获得二星;
-
如果索引中的列包含了查询中需要的全部列则获得三星。
二星(排序星):
在满足一星的情况下,当查询需要排序,group by、 order by,如果查询所 需的顺序与索引是一致的(索引本身是有序的),是不是就可以不用再另外排序 了,一般来说排序可是影响性能的关键因素。
三星(宽索引星):
在满足了二星的情况下,如果索引中所包含了这个查询所需的所有列(包括 where 子句 和 select 子句中所需的列,也就是覆盖索引),这样一来,查询就 不再需要回表了,减少了查询的步骤和 IO 请求次数,性能几乎可以提升一倍。
一星按照原文稍微有点难以理解,其实它的意思就是:如果一个查询相关的 索引行是相邻的或者至少相距足够靠近的话,必须扫描的索引片宽度就会缩至最 短,也就是说,让索引片尽量变窄,也就是我们所说的索引的扫描范围越小越好。
这三颗星,哪颗最重要?第三颗星。因为将一个列排除在索引之外可能会导 致很多磁盘随机读(回表操作)。第一和第二颗星重要性差不多,可以理解为第 三颗星比重是 50%,第一颗星为 27%,第二颗星为 23%,所以在大部分的情况下, 会先考虑第一颗星,但会根据业务情况调整这两颗星的优先度。
达成三星索引
现在有表
create table customer(
cno int, lname varchar(10),
fname varchar(10),
sex int,
weight int,
city varchar(10)
);
建立索引
create index idx_cust on customer(city,lname,fname,cno);
对于下面的 SQL 而言,这是个三星索引
select cno,fname from customer where lname =’xx’ and city =’yy’ order by fname;
来评估下:
**第一颗星:**所有等值谓词的列,是组合索引的开头的列,可以把索引片缩得 很窄,符合。
**第二颗星:**order by 的 fname 字段在组合索引中且是索引自动排序好的,符 合。
**第三颗星:**select 中的 cno 字段、fname 字段在组合索引中存在,符合。
达不成三星索引
现在有表
CREATE TABLE `test` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`user_name` varchar(100) DEFAULT NULL,
`sex` int(11) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`c_date` datetime DEFAULT NULL,
PRIMARY KEY (`id`),
) ENGINE=InnoDB AUTO_INCREMENT=12 DEFAULT CHARSET=utf8;
SQL 语句如下:
select user_name,sex,age from test where user_name like 'test%' and sex =1 ORDER BY age
如果我们建立索引(user_name,sex,age):
第三颗星,满足
第一颗星,满足
第二颗星,不满足,user_name 采用了范围匹配,sex 是过滤列,此时 age 列 无法保证有序的。(只要排在前面的列不是固定值,使用后面的排序将总是不能保证有序的)
上述我们看到,此时索引(user_name,sex,age)并不能满足三星索引中的第二 颗星(排序)。
于是我们改改,建立索引(sex, age,user_name):
第一颗星,不满足,只可以匹配到 sex,sex 选择性很差,意味着是一个宽 索引片,
第二颗星,满足,等值 sex 的情况下,age 是有序的,
第三颗星,满足,select 查询的列都在索引列中,
对于索引(sex,age,user_name)我们可以看到,此时无法满足第一颗星,窄 索引片的需求。
以上 2 个索引,都是无法同时满足三星索引设计中的三个需求的,我们只能 尽力满足 2 个。而在多数情况下,能够满足 2 颗星,已经能缩小很大的查询范围 了,具体最终要保留那一颗星(排序星 or 窄索引片星),这个就需要看查询者 自己的着重点了,无法给出标准答案。
主键是很少改变的列
我们知道,行是按照聚集索引物理排序的,如果主键频繁改变(update),物理顺序会改变,MySQL 要不断调整 B 树,并且中间可能会产生页面的分裂和合并等等,会导致性能会急剧降低。
冗余和重复索引
MySQL 允许在相同列上创建多个索引,无论是有意的还是无意的。MySQL 需要单独维护重复的索引,并且优化器在优化查询的时候也需要逐个地进行考虑, 这会影响性能。重复索引是指在相同的列上按照相同的顺序创建的相同类型的索 引。应该避免这样创建重复索引,发现以后也应该立即移除。
有时会在不经意间创建了重复索引,例如下面的代码:
CREATE TABLE test (
ID INT NOT NULL PRIMARY KEY,
A INT NOT NULL,
B INT NOT NULL,
UNIQUE(ID),
INDEX(ID)
) ENGINE=InnoDB;
这里创建了一个主键,又加上唯一限制,然后再加上索引以供查询使用。事 实上,MySQL 的唯一限制和主键限制都是通过索引实现的,因此,上面的写法实 际上在相同的列上创建了三个重复的索引。通常并没有理由这样做,除非是在同 一列上创建不同类型的索引来满足不同的查询需求。
冗余索引和重复索引有一些不同。如果创建了索引(A B),再创建索引(A)就 是冗余索引,因为这只是前一个索引的前缀索引。因此索引(AB)也可以当作索引 (A)来使用(这种冗余只是对 B-Tree 索引来说的)。但是如果再创建索引 (B,A), 则不是冗余索引,索引(B)也不是,因为 B 不是索引(A,B)的最左前缀列。
(出现(a b) (a) 这种索引的现象很常见, 例如前一个开发按照自己的需求建立了一个a索引,随着时间的推移和需求的变化,另一个程序员为了提高自己SQL的性能,发现需要添加一个(a b)索引,但是由于他没有注意到之前有一个(a)索引或者并不这道这个(a)索引是冗余的,所以没有移除冗余的(a)索引, 所以我们应该在创建索引的同时注意维护历史索引,做一个有"素质"的程序员)
解决冗余索引和重复索引的方法很简单,删除这些索引就可以,但首先要做 的是找出这样的索引。可以通过写一些复杂的访问 INFORMATION_SCHEMA 表的 查询来找。
删除未使用的索引
除了冗余索引和重复索引,可能还会有一些服务器永远不用的索引。这样的 索引完全是累赘,建议考虑删除。
面试题
-
为什么 MySQL 的索引要使用 B 树而不是 B 树?
高度可控和数据顺序访问
-
InnoDB 一棵 B 树可以存放多少行数据?
计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。在计算机中磁盘存储数据最小单元是扇区,一个扇区的 大小是 512 字节,而文件系统(例如 XFS/EXT4)他的最小单元是块,一个块的 大小是 4k(所以经常听到4k对齐),而对于我们的 InnoDB 存储引擎也有自己的最小储存单元——页 (Page),一个页的大小是 16K。Innodb 的所有数据文件(后缀为 ibd 的文件), 他的大小始终都是 16384(16k)的整数倍。
-rw-r-----. 1 mysql mysql 25165824 Dec 8 08:04 mysql.ibd 25165824/16384 = 1536 -rw-r-----. 1 mysql mysql 131072 Dec 8 07:07 users.ibd 131072/16384 = 8 = 128k
数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢? 假设一行数据的大小是 1k,那么一个页可以存放 16 行这样的数据。
对于 B 树而言,只有叶子节点存放数据,非叶子节点存放的是只保存索引 信息和下一层节点的指针信息。一个非叶子节点能存放多少指针?
其实这也很好算,我们假设主键 ID 为 常用的 bigint 类型,长度为 8 字 节,而指针大小在 InnoDB 源码中设置为 6 字节,这样一共 14 字节,我们一 个页中能存放多少这样的单元,其实就代表有多少指针,即 16384/14=1170 个。
那么可以算出一棵高度为 2 的 B 树,存在一个根节点和若干个叶子节点能 存放 1170*16=18720 条这样的数据记录。
根据同样的原理我们可以算出一个高度为 3 的 B 树可以存放: 1170*1170*16=21902400 条这样的记录。
所以在 InnoDB 中 B 树高度一般为 1-3 层,就能满足千万级的数据存储。
那么为什么 MySQL 的索引要使用 B 树而不是 B 树?
而 B 树和 B 树的最大区别就是,B 树不管叶子节点还是非叶子节点,都会 保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出(所以非叶子节点不存数据也是为了增加扇出,减少高度,提高查询速度)),指针少的情况下要保存大量数据,只能增加树的高度,导致 IO 操作变多, 查询性能变低。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgcgjea
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13