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

相关文章

来自专栏c#开发者

C# : row-clickable GridView and get and set gridview rows using JavaScript

Complete C# code: ---------------- using System; using System.ComponentModel; ...

2966
来自专栏菩提树下的杨过

SqlTransaction事务使用示例

using System; using System.Data; using System.Data.SqlClient; using System.Co...

1828
来自专栏码匠的流水账

聊聊spring cloud的AbstractLoadBalancingClient

本文主要研究一下spring cloud的AbstractLoadBalancingClient

812
来自专栏CreateAMind

文字描述生成视频的开源项目

Tensorflow implementation for the paper Attentive Semantic Video Generation usin...

1072
来自专栏玩转JavaEE

RestTemplate的逆袭之路,从发送请求到负载均衡

上篇文章我们详细的介绍了RestTemplate发送请求的问题,熟悉Spring的小伙伴可能会发现:RestTemplate不就是Spring提供的一个发送请求...

1.1K4
来自专栏菩提树下的杨过

winform中linkLabel的用法(示例)

private void Form1_Load(object sender, EventArgs e)         {             this...

1895
来自专栏码匠的流水账

聊聊EurekaRibbonClientConfiguration

spring-cloud-netflix-eureka-client-2.0.0.RELEASE-sources.jar!/org/springframewor...

1111
来自专栏c#开发者

jquery easyui datagrid mvc server端分页排序筛选的实现

1自定义一个ModelBinder public class filterRule { public string field { g...

4169
来自专栏谈补锅

记录C#常用的代码片段

using Newtonsoft.Json; using Newtonsoft.Json.Linq;

882
来自专栏跟着阿笨一起玩NET

C#巧用Excel模版变成把Table打印出来

转载:http://blog.csdn.net/gwblue/article/details/38865525

1122

扫码关注云+社区