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

相关文章

来自专栏牛客网

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

23100
来自专栏Aloys的开发之路

OOAD与UML笔记

UML基础介绍 1.UML的定义 统一建模语言(UML)是一种图形化的语言,它可以帮助我们在OOAD过程中标识元素、构建模块、分析过程并可通过文档说明系统中的重...

20680
来自专栏数据派THU

一文盘点三大顶级Python库(附代码)

Python在许多方面有着强大的吸引力 - 例如效率、代码可读性和速度方面,也正因为如此,对于希望提升应用程序功能的数据科学家和机器学习专家来说,Python通...

23540
来自专栏GopherCoder

专栏:009:高评分电影都在这里

17820
来自专栏机器之心

资源 | 知网(HowNet)知识库的简单调用指南

机器之心整理 参与:蒋思源 机器之心曾采访过语知科技的董强先生,在那一篇文章中,我们详细讨论了基于知网知识库的 NLP 解决方案。虽然我们已经了解了这种方法的潜...

78650
来自专栏HansBug's Lab

洛谷讲课手稿

Hello大家好,我是洛谷的HansBug。首先自我介绍下,我现在在北京航空航天大学,计算机科学与技术专业读大二,我参加过2013-2015年的提高组NOIP和...

33040
来自专栏battcn

一起学设计模式 - 策略模式

策略模式: 是对算法的包装,是把使用算法的责任和算法本身分割开来,委派给不同的对象管理。策略模式通常把一个系列的算法包装到一系列的策略类里面,作为一个抽象策略类...

9620
来自专栏牛客网

cvte面经

一面:现场面去的很早明显焦虑并问不到面经(50分钟) (1)自我介绍这里介绍完提到自己熟悉的知识,项目 (2)项目介绍项目中遇到的难点如何解决的 (3)集合框架...

39470
来自专栏小樱的经验随笔

元胞自动机实现多数分类算法

元胞自动机(Cellular automaton) 元胞自动机是由元胞组成的网格,每个元胞都根据邻域的状态来选择开或关。所有的元胞都遵循同样的规则,也称为元胞的...

34850
来自专栏逸鹏说道

借网站日记分析~普及一下Pandas基础

对网站日记分析其实比较常见,今天模拟演示一下一些应用场景,也顺便说说Pandas,图示部分也简单分析了下

7230

扫码关注云+社区

领取腾讯云代金券