性能优化:认识B*Tree 索引分裂(二)

黄玮(Fuyuncat)

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

编辑手记:正确的认识问题是处理问题的第一步,前面的分享中我们认识了索引分裂的方式及类型,这次我们继续来认识索引分裂之树的生长。

树的生长

当分裂导致B树索引的层数(Btree Level)增加时,我们称之为树的“生长”。当叶子节点分裂时,在其父节点上需要增加一条记录指向新节点,如果此时父节点上没有足够空间,则父节点也会发生分裂,如果如此递归下去,直到根节点也分裂,那么索引的高度就增加了。

下图为一次9-1分裂导致的树的增长:

上面的分裂过程中,节点Root、B5、B3和L4在数据插入前都已经饱和,当数据插入时,导致这4个节点发生连锁的分裂,最终root的分裂会分配两个新枝节点,分别为其左右枝节点,由于L4、B3、B5都是发生9-1分裂,在新分裂的数据块上没有被转移老数据,它们都被放到了新生的右枝上了。

在每一个枝节点中,都有且只有一个左指针指向其下一层的左节点。这个指针很特殊,它存储于枝节点的头部而非数据区,其节点的键值是枝节点中唯一小于枝节点的键值据、且不被存储。枝节点中其它的所有指针我们都称为右指针(即其节点键值大于等于枝节点的键值,且都有相应记录存储)。在节点分裂过程中,始终会保证每一个枝节点的左节点都有数据。

由于左节点的特殊性,仅仅按照之前的分裂条件,当向左枝节点左侧插入数据时,即使其兄弟右枝节点数据区中没有数据(即只有左节点、没有右节点),它们的父节点都会分裂,在特殊情况下(所有左枝节点都饱和,但右枝节点下没有数据),索引高度会加,但底层枝节点下很空,叶子节点很少。甚至于特殊情况下(索引数据块为2K、键值数据长度大于1K),叶子节点数可以等于索引高度。这一算法缺陷在9i及之前版本都存在,如下图所示:

分裂前,所有左枝节点、叶子节点都已经饱和,左分裂造成连锁分裂,促成树的增长。如果键值为特殊数据、数据块为2K的话,此次分裂后,所有左节点仍然保持饱和状态——意味下一次的左插入会继续导致树的增长。

在10g中,这个缺陷被修正了:当左枝节点已经饱和时,会先检查其兄弟右枝节点是否为空,如果为空,则将左枝节点的部分数据(5-5)转移到右枝节点,从而避免左枝节点的分裂,如下图所示:

这一算法的修正避免了左分裂造成树的迅速增长。

--- Fuyuncat TBC ---

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SAP最佳业务实践

想学FM系列(20)-SAP FM模块:派生规则推导策略(3)-派生规则推导步骤-派生规则、增强

4.1.4 派生规则 派生规则简单来讲由通过枚举条件的值来推导出目标字段的值。比如已知一个变量作为条件,枚举变量值为:V1、V2……,再枚举出目标变量对等值为:...

4987
来自专栏有趣的Python

玩转算法面试:(一)什么是算法面试?

前言 对于面试中遇到的大多数问题 都能有一个合理的思考路径 沟通: 边界条件是怎样的? 数据范围如何? 某些术语是具体如何定义的? ? 基础数据结构 算法设...

3679
来自专栏牛客网

测开面经

楼主语言是python+c ,专业是通信工程、985硕 初始找工作倾向于python后台,但一直没得及自己独立开发项目,所以没底气。面经按照面试的时间顺序写的。...

3865
来自专栏ACM算法日常

新手ACM算法学习建议

一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功。ACM主要是考算法的,主要时间是花在思考算法上,不是花在写程序与debug上。

783
来自专栏小小挖掘机

数据城堡参赛代码实战篇(一)---手把手教你使用pandas

小编们最近参加了数据城堡(http://www.pkbigdata.com/)举办的“大学生助学金精准资助预测”比赛,分组第19名的成绩进入了复赛,很激动有木有...

3034
来自专栏C语言及其他语言

OJ系统(ACM/NOI)的基本输入输出教程

在介绍OJ系统之前,首先为大家介绍一下ACM: ACM原代表美国计算机协会,因其举办的ICPC即国际大学生程序设计竞赛而闻名全世界,此项赛事要求学生的在五小时内...

36412
来自专栏ATYUN订阅号

一文教你提高算法和数据结构技能

? 如果你想在算法和数据结构上做得更好,你首先需要做的就是建立一个坚实的基础。这个基础可以通过多种方式学习,通过大学的计算机科学课程,或者参加一些编程训练营,...

2716
来自专栏编程一生

看Lucene源码必须知道的基本规则和算法

843
来自专栏数据科学与人工智能

【数据挖掘】图数据挖掘

互联网发展至今,数据规模越来越大,数据结构越来越复杂,而且对系统的需求越来越高。如果学习过数据结构,那么都知道图是放在最后一个结构,当你学习了图,那么应该感知到...

2258
来自专栏牛客网

2018年5月23日滴滴新锐实习电话面试,开发岗位

1930

扫描关注云+社区