性能优化:认识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 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

如何用纯SQL查询语句可以实现神经网络?

在这篇文章中,我们将纯粹用SQL实现含有一个隐藏层(以及带 ReLU 和 softmax 激活函数)的神经网络。这些神经网络训练的步骤包含前向传播和反向传播,...

1133
来自专栏瓜大三哥

多任务验证码识别

使用Alexnet网络进行训练,多任务学习:验证码是根据随机字符生成一幅图片,然后在图片中加入干扰象素,用户必须手动填入,防止有人利用机器人自动批量注册、灌水、...

4497
来自专栏瓜大三哥

直方图操作(四)

直方图操作(四) 之清零电路 一种简单的方法是在所有数据输出完成之后整体清零,另一种思路是在输出完成的下个时钟清零,清零地址为递增,由B口输入。 本设计采用反相...

20110
来自专栏机器之心

教程 | 没错,纯SQL查询语句可以实现神经网络

选自Medium 作者:Harisankar Haridas 机器之心编译 参与:陈韵竹、思源 我们熟知的SQL是一种数据库查询语句,它方便了开发者在大型数据中...

3684
来自专栏谭正中的专栏

TensorFlow 入门(2):使用DNN分类器对数据进行分类

本文作者通过分析《高级API入门教程》这篇文章中的实例:教我们如何使用DNN(深度神经网络)分类器实现对鸢尾花的分类,并对其提出举一反三的案例,提升学习效果,并...

10.1K4
来自专栏杨熹的专栏

用 Pipeline 将训练集参数重复应用到测试集

当我们对训练集应用各种预处理操作时(特征标准化、主成分分析等等), 我们都需要对测试集重复利用这些参数。 pipeline 实现了对全部步骤的流式化封装和管理...

3337
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列十一:使用FFT变换实现图像卷积。

  本文重点主要不在于FFT的SSE优化,而在于使用FFT实现快速卷积的相关技巧和过程。   关于FFT变换,有很多参考的代码,特别是对于长...

3529
来自专栏ml

机器学习之KNN算法思想及其实现

从一个例子来直观感受KNN思想 如下图 , 绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色...

39513
来自专栏章鱼的慢慢技术路

用OpenGL进行立方体表面纹理贴图

1573
来自专栏数据结构与算法

19:救援

19:救援 总时间限制: 1000ms 内存限制: 65536kB描述 救生船从大本营出发,营救若干屋顶上的人回到大本营,屋顶数目以及每个屋顶的坐标  和人数...

3419

扫码关注云+社区