数据库索引设计与优化08-索引和索引重组

B树索引的物理结构

在前面,索引被描述为一个表,该表包含了其所属表的列的子集,连同指向表行的指针一起。我们假设DBMS可以直接定位带匹配列所定义的索引片的第一行,然后继续扫描,知道发现一行不满足匹配列条件的索引行时停止。之前都是假设一个索引行对于一个表行,即使是索引不唯一的时候也是如此。而且,索引行总是以索引列所定义的顺序来显示的。当通过计算访问次数来评估索引时,在脑海中有这么一个假设是非常重要的。不过B树索引的真实物理结果并不是如此。

索引行被存储在索引的叶子页上。典型的索引页的大小为4KB或8KB。索引行的长度一般为索引列的总长度外加约10个字节的控制信息。如果索引行的长度为200字节,并且索引为唯一索引,那么一个8KB的叶子页大约可以存放40个索引行。如果是非唯一索引,每个索引键值后可能会有多个指针,在许多DBMS产品中,这些指针会以其值的顺序来存储。这样即使同一个索引键值对应100万条记录,DBMS也能够快速的找到那个需要删除的指针。

DBMS如何查找索引行

SQL 11.1

SELECT COLX
FROM TABLE
WHERE COLI = 12

假设优化器决定使用索引COLI来执行SQL 11.1。

DBMS首先通过内部系统表找到指向根页的指针,在读取根页之后,DBMS需要读取第二个叶子页来查找与键值12相关联的指针。

一次随机读取会从磁盘上读取一个页。如果系统表中那些用于定位根页的表页已经在数据库缓冲池中,那么这个查询可能需要进行三次随机读 : 一次根页,一次叶子页及一次表页。然而,在当前的硬件条件下,非叶子页很可能已经被缓存在数据库缓冲池中,或者至少在磁盘的读缓存中,因为它们经常被频繁的访问。所以,很有了可能只会产生两次随机读,改查询的的同步I/O时间约为2 x 10ms = 20ms,在当前的处理器条件下,CPU时间相对小得多,所以该查询的还是很可能就在20ms左右。

当数据库需要读取一个索引片时,如上述他会先读取第一个索引行。第一个索引行有一个指针指向下一个索引行,DBMS会一致沿着这个指针链访问,直到遇到一个不满足匹配谓词的索引行为止。所有的索引行都通过索引值链在一起。

在SQL 11.2中,SELECT语句所要查找的是LNAME以字符串“JO”开始,且CITY以字符串“LO”开始的记录。在这一场景下,DBMS会首先在键值JO后追加字母“A”至最大长度,如JOAA...AAA,尝试用该值在索引(LNAME, CITY)上找到一行记录。
SQL 11.2

DECLARE CURSOR112 CURSOR FOR
SELECT CNO, FNAME
FROM CUST
WHERE LNAME BETWEEN :LNAME1 AND :LNAME2
      AND
      CITY BETWEEN :CITY1 AND :CITY2
ORDER BY FNAME

当找到该键值在索引上的位置后,DBMS随之通过链表读取后续的索引行,直至一个不以“JO”开始的索引行为止。

插入一行会发生什么

如果一张表有一个聚簇索引,那么DBMS会根据聚簇索引的键值尝试将插入的记录放在它所属的表页(主页)中。如果这行记录在主页里放不下,或者当前页被锁住,那么DBMS将会检查邻近的页。在最坏的情况下,新的行会被插入到标的最坏一页。依赖于DBMS和表的类型,已经插入的行通常都不会被移动,否则这将意味着更新表上已经建立的所有索引上的相关指针。当有许多表行未能存在在主页中时,如果表行的顺序很重要,则需要对这个表进行重组---对于那些涉及多张大表的大规模批处理任务而言,通常需要这么做。

当往表中插入一条记录时,DBMS会尝试将索引行添加至其索引建所属的叶子页上,但是该索引页可能没有足够的空闲空间来存放这个索引行,在这种情况下,DBMS将会分裂该叶子页。其中一半的行将被移动到一个新的叶子页上,并尽可能地靠近被分裂的页,但是在最坏的情况下,这个索引页可能会被放置在索引的末尾。除了在每个叶子页上预留部分比例的空闲空间外,也许可以在索引被创建或重组时,每n个页面预留一个空页---当索引分裂无法避免时,这会是一个不错的办法。

叶子页的分裂验证吗

分裂一个索引页只需一次额外的同步读,约10ms。除了两个叶子页以外,DBMS通常还必须更新一个非叶子页,而它很可能已经在内存或者读缓存中了。

在叶子页分裂后,查询任何一条索引行的速度很可能同之前一样快。在最坏情况下,一次分裂会创建一个新的索引层级,但是如果不是从磁盘读取非叶子页的话,这只会增加很少的CPU时间。

然而,叶子页的分裂会导致一个索引片变得更慢。目前为止,我们在所有的场景中都假设串联索引行的链指针总是指向同一页或者下一页,这些页可能已被DBMS预读取。在索引被创建或者重组后,这种假设是接近真实情况的,但是索引片上的每处叶子页分裂都可能会增加额外的两次随机访问---一次是为了查找索引行被移动至的索引页,一次是为了返回到扫描的原始位置。其中第一次随机访问很可能会导致一次磁盘的随机读取(10ms)。

假设我们需要扫描100000个索引行,根据QUBE,这将花费
1 x 10ms + 100000 x 0.01ms ≈ 1s

当每个叶子页包含20个索引行(不存在叶子页分裂)时,DBMS必须读取5000个叶子页。如果这些是相邻的,并且顺序读的速度为0.1ms每页(40MB/s,页大小为4KB),那么I/O时间为 :
10ms + 5000 x 0.1ms = 510ms

如果1%的叶子页发生过分裂,扫描100000个索引行可能需要进行50次随机I/O(5000的1%)。即便是这样很小比例的分裂,I/O时间也增加了一倍 :
51 x 10ms + 5000 x 0.1ms = 1010ms

在叶子页分裂后,计算索引片扫描的I/O时间的通用公式为
(1 + (LPSR x A/B)) x ORIG

LPSR : 叶子页的分裂比率(分裂的数量/叶子页的数量)
A : 单次随机读的I/O的时间
B : 单次顺序读的I/O的时间
ORIG : 无叶子页分裂时的I/O时间

这个公式基于两个假设 :

  1. 顺序I/O时间为NLP x B(访问第一个子叶的随机I/O忽略不计)
  2. 随机I/O时间为LPSR x NLP x A(每个叶子页分裂涉及一次随机I/O)

随着A/B的增加,叶子页分类比例的预警阈值在不断降低。当A/B = 100(假设)时,若LPSR达到1%,那么I/O时间就翻倍了。

什么时候应该对索引进行重组

插入模式

索引重组是为了恢复索引行正确的物理位置,他对于索引片扫描和全索引扫描的性能而言很重要。因为插入模式的不同,增加的索引行可能会以无序的方式来创建。我们需要记住,更新一个列意味着需要删除旧的索引行,并增加一个新的索引行,新索引行的位置由新的索引键值来确定。

下文对三种基本插入模式的讨论基于如下假设

  1. 索引是唯一索引。
  2. 被删除的索引行锁腾出的空间在重组之前可以被新的索引行重用。

新索引行被添加至索引的尾部(永远递增的键)

假设插入了一个索引行,其索引键值比任何已经存在的索引键值都要大,则DBMS就不会分类最后的叶子页,那么就不需要空闲的空间或者进行索引重组了。然而,如果在索引前面的索引行被定期地删除,那么为了回收空闲的空间,索引可能不得不进行重组(一个“爬行”的索引)。

有一个重要的例外场景 : 如果索引行是变长的,那么就需要有空闲的空间去适应任何索引行的增长。

随机插入模式

我们稍后将会看到,尽管考虑了空闲空间和重组,对于不同的索引行长度(短,中,长)的处理也是不同的。越长的索引行越难处理,越短的越好处理。

索引页大小索引类型索引大小
4KB< 80字节
8KB< 160字节
4KB中等80 ~ 200字节
8KB中等160 ~ 400字节
4KB> 200字节
8KB> 400字节

短索引行的选择捷径

当索引行比较短时,为一个随机插入情况的索引选择P值是相对简单的。
基本建议 : P = 10%,当索引已经增长超过5%时重组索引
略。。。

标签: mysql, mysql索引

添加新评论