性能优化:认识B树索引分裂

黄玮(Fuyuncat)

黄玮(Fuyuncat),资深 Oracle DBA,从事Oracle数据库管理、维护与开发工作十余年,有丰富的大型数据库设计、开发与维护方面的经验,涉及航空、水利、军工、电信等多个行业。曾供职于某世界著名物流公司,负责公司的电子物流系统的数据库开发和维护工作。2005年创建了个人网 www.HelloDBA.com,致力于数据库底层技术的研究,整理和发布了大量关于数据库系统底层机制、存储结构、性能调优以及基础算法方面的文章,获得广大同行的高度评价。

编辑手记:知己知彼,百战不殆。最强大的敌人无知。在数据库运维中,索引分裂是很常见的问题,这一期我们就跟随作者的脚步去认识索引分裂,为以后的索引维护打好基础。

如何分裂

当一个事务需要修改(大多数情况是Insert操作,某些情况下也可能为 Delete 操作)索引块(枝节点或叶子节点)上的数据,但没有足够空间容纳新的数据(包括索引条目、ITL slot)时,会将原有块上的部分数据放到一个新的数据块上去,这一过程就是索引块分裂(Index Block Splitting)。

按照分裂的对象不同,分为叶子节点分裂和枝节点分裂,而枝节点分裂中还有一个特殊的分裂:根节点分裂。

按照分裂时,2个数据块上分布的数据比例,分为5-5分裂和9-1分裂:

§ 5-5分裂:新旧2个数据块上的数据基本相等;

§ 9-1分裂:大部分数据还在原有数据块上,只有少量数据被转移到新的数据块上。

1) 叶子节点分裂

当 Insert、Update(实际上就是 Delete+Insert)时,叶子节点块上没有足够空间容纳新的索引条目,就会发生叶子节点分裂:

在10224事件的 trace 文件中可以看到叶子节点块分裂的记录:

同时,将 Btree 结构 dump 出来,也可以看到节点被分裂:

2、当事务需要修改节点上的数据,叶子节点上没有足够空间容纳新的 ITL slot 时,也会发生分裂。

我们 dump 出一个“满”的节点,注意到它上面的空闲空间只有20字节,小于一条 ITL slot的大小(24字节)

并且此时它里面有一条空闲 ITL slot(第一条ITL slot是用于递归事务的,后面会有解释),先用一个事务占用它:

然后再启动一个事务,造成了空间不足分配新的 ITL slot,而导致节点分裂:

在10224 trace文件中记录此次分裂:

枝节点分裂

枝节点的下一层的节点分裂,会导致在枝节点上增加一条记录指向新增加的节点,当此时枝节点上空间不足时,会导致枝节点分裂。 这种情况很容易被重现,我们这就不放 demo 代码了,下面是 trace 文件中记录的枝节点分裂:

要注意的是,枝节点中存储的数据是比较特殊的,因而数据的分布会直接影响到枝节点的多少以及其分裂的频率。

在枝节点中,每条记录指向了下一层一个节点上的最小值,但其并不一定完整的存储了索引字段上的数据:

对于单个字段,如果字段的前面一部分数据就可以定位到下一层的节点块,则枝节点中只存储这一部分数据;例如,字段A的索引节点的第一个叶子节点上的字段数据是 AAA11111, AAA22222, .... AAA55555;第二个节点上的字段数据是 AAA66666,....AAA99999,那么,在枝节点上分别存储的数据是 AAA1 和 AAA6

对于复合字段索引,如果前面字段已经可以定位到下一层的节点块,则枝节点中只存储这些字段,而不存储后面的字段值。例如,在字段(A, B)上建立了索引,A的值是自增长的,所以通过A就可以定位到下一层的节点,在枝节点上就只存储了A的数据:

我们将一个枝节点 dump 出来,可以看到B字段的数据没有被记录:

正因为枝节点的这种的索引值的存储方式,在下面例子中,字段在索引中的顺序不同直接导致了索引的高度不同:

可以看到,idx_split_idx1和idx_split_idx2 中的字段是一样的,因此它们的叶子节点数也是一样的,但是因为它们的数据分布性不同以及在索引中的位置不相同,导致它们的枝节点的数量和索引高度有很大的差别。同时,通过 10224 事件的 trace 文件也可以看到,发生在 idx_split_idx2 上的枝节点分裂次数远远多余在 idx_split_idx1上发生的次数。

根节点分裂——特殊的枝节点分裂

在所有枝节点中,有一个特殊的枝节点(或许你可以将它作为一种单独的节点类别),那就是根节点。根节点上的数据已经导致根节点分裂的条件基本上和普通枝节点相同,但是,唯一不同的是,普通枝节点或叶子节点在分裂时,只分配一个新的数据块,然后将被分裂的数据块上的部分数据转移到新的数据块上去,而根节点的分裂是需要分配2个新的数据块,将原有数据分别转移到2个新的数据块上去,在原有节点上生成2条记录分别指向这2个新的数据块。下面的Trace记录的就是根节点的分裂,可以看到它获取了2个新的数据块:

9-1分裂

当事务向索引中最后一个叶子节点数据块上插入一条大于或等于(ROWID 大于最大值的ROWID)数据块上最大值的数据,且该数据块上不存在其它未提交事务时,此时如果没有足够空间,就会发生9-1分裂:即分裂时,绝大部分数据保留在原有节点数据块上,仅少量数据被转移到新数据块上。

注意:当向索引中插入大于、等于最大值的数据时,PCTFREE 会被忽略(我们在后面会介绍索引中 PCTFREE 和 INITRANS 的影响)

注意2:如果叶子节点分裂导致枝节点也分裂,枝节点的分裂比例和叶子节点的分裂比例是相同的。

下面例子中,枝节点和叶子节点都发生了9-1分裂:

注意,这里的统计结果中,枝节点的分裂方式并未显示,但从 Trace 文件中可以看到,新分裂的节点数据块上只有少量数据,发生的是9-1分裂:

5-5分裂

有3种情况会导致5-5分裂:

  1. 当新插入的数据小于索引中的最大值时,此时数据块空间不足容纳新的键值;
  2. 当插入、删除数据时,数据块上没有足够空间分配新的ITL slot;
  3. 当新插入的数据大于或等于索引中最大值时,此时数据块上还存在其它未提交的事务。

第一种情况很常见,这里不举例了。第二种情况可以参见之前的例子。下面代码是第三种情况的例子代码:

可以看到该分裂为5-5分裂,从索引树结构上也可以看出:

实际上,无论是9-1分裂还是5-5分裂,其目的都是为了减少分裂,因为节点分裂是一个代价高昂的操作:

  • 当发生9-1分裂时,通常是索引的键值是递增的,且表上的主要操作为插入操作、事务并发量比较低的情况。保证新的数据块上有最大的空闲空间插入新值,因而减少了分裂的发生;
  • 发生5-5分裂时,通常表上的并发事务较多,且插入、删除的数据比较分散,因此需要保持分裂的新、老数据块上有相当的空闲空间以容纳新事务、新数据。

--- Fuyuncat TBC ---

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2016-08-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏匠心独运的博客

数据库技术之记一次排查DB死锁的分析与思考

虽然很多童鞋在学数据库课程时都了解数据库隔离级别、死锁和事务等概念,但在测试/线上环境遇到死锁却不一定能够及时分析并解决这类问题。本文主要以作者在测试环境中遇到...

521
来自专栏PPV课数据科学社区

SQL Server优化50法

查询速度慢的原因很多,常见如下几种: 1、没有索引或者没有用到索引(这是查询慢最常见的问题,是程序设计的缺陷) 2、I/O吞吐量小,形成了瓶颈效...

3117
来自专栏Java Web

Java 面试知识点解析(六)——数据库篇

在遨游了一番 Java Web 的世界之后,发现了自己的一些缺失,所以就着一篇深度好文:知名互联网公司校招 Java 开发岗面试知识点解析 ,来好好的对 Jav...

2569
来自专栏数据和云

Oracle 12.2新特性掌上手册 - 第七卷 Big Data and Data Warehousing

编辑手记:也许Oracle 12.2在内核上的智能改进只能让你眼前一亮,那今天基于Big Data和数据仓库的性能优化增强则会让你伸手触Oracle的强大灵魂。...

2747
来自专栏magicsoar

Mysql Innodb 锁机制 select * from table where?insert?delete?update?3个insert的死锁2个update的死锁3个以上delete的死

latch与lock latch 可以认为是应用程序中的锁,可以称为闩锁(轻量级的锁) 因为其要求锁定的时间必须要非常短,若持续时间长,则会导致应用性能非常差,...

2618
来自专栏张善友的专栏

SQL Server数据库碎片

当索引所在页面的基于主关键字的逻辑顺序,和数据文件中的物理顺序不匹配时,碎片就产生了。所有的叶级页包含了指向前一个和后一个页的指针。这样就形成一个双链表。理想情...

1708
来自专栏乐沙弥的世界

db_block_checking与db_block_checksum

    db_block_checking与db_block_checksum两个参数都是对block进行检查,然而两者很容易混淆。事实上,两个参数中前者是对块...

703
来自专栏鸿的学习笔记

一条SQL生命历程

1.一条SQL的诞生首先需要通过某种方式传递给数据库。数据库会有一个客户端用来与外界交流,而作为提交SQL的一方,可以通过ODBC或者是JDBC协议直接将SQL...

1124
来自专栏Java Web

Java 面试知识点解析(六)——数据库篇

1233
来自专栏Hadoop数据仓库

HAWQ技术解析(八) —— 大表分区

一、HAWQ中的分区表         与大多数关系数据库一样,HAWQ也支持分区表。这里所说的分区表是指HAWQ的内部分区表,外部分区表在后面“外部数据”篇讨...

2107

扫描关注云+社区