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

相关文章

来自专栏coolblog.xyz技术专栏

科普:String hashCode 方法为什么选择数字31作为乘子

某天,我在写代码的时候,无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现,发现并不是很复杂。但是我从源码中发现了一...

54818
来自专栏wym

HDU 1166 敌兵布阵

http://acm.hdu.edu.cn/showproblem.php?pid=1166

702
来自专栏DannyHoo的专栏

iOS开发中使用算法之二分搜索算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

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

[每日一题]矩阵转置(1242)

题目描述 输入N*N的矩阵,输出它的转置矩阵。 输入 第一行为整数N。 接着是一个N*N的矩阵。 输出 转置矩阵 样例输入 2 1 2 1 2 样例输出 1 ...

3119
来自专栏工科狗和生物喵

【计算机本科补全计划】CCF计算机职业资格认证 2016-04-1/2(俄罗斯方块)详解

正文之前 果然,上一篇文章结尾的预言果然一语成谶,2016-09-4我果然没做出来。没错,昨晚到现在都没有做出来,当然,也是我做了一晚上心灰意冷,然后去欺负本文...

3799
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

3305
来自专栏人工智能头条

MXNet设计笔记之:深度学习的编程模式比较

1803
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

801
来自专栏北京马哥教育

Numpy 隐含的四大陷阱,千万别掉进去了!

看起来效果不错。假设我们要对数据进行筛选,取第 1 列的第 1 行和第 3 行数据构成一个 2 x 1 的列向量。先看对 array 的做法:

841
来自专栏Linyb极客之路

浅谈黑盒测试和白盒测试

  从图中可以直接看出来,黑盒测试就当整个程序是个黑盒子,我们看不到它里面做了些什么事情,只能通过输入输出看是否能得到我们所需的来测试。而白盒测试可以当盒子是透...

1011

扫码关注云+社区