ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 关于索引叶子块分裂方式的研究(一)

关于索引叶子块分裂方式的研究(一)

原创 Linux操作系统 作者:realkid4 时间:2012-07-09 20:56:40 3 删除 编辑

 

索引的构建过程是一个Oracle形成B*树的过程。在进行数据表DML操作的时候,索引树要随着索引列的变化进行同步的更新。当我们的数据表不断增加容量,对应的索引树也在进行不断的广度拓展和深度拓展。

 

站在Oracle逻辑存储结构的角度,Index是对应Segment在索引拓展的过程中也是一个不断拓展、分配新extent的过程。由于索引叶子节点对应是有序列值序列,那么不断插入新数据的过程,必然要伴随着索引叶子块的分裂过程。本系列中,我们就一起来研究一下分裂过程中使用的算法和相应规则。

 

1、索引叶子块分裂的两种算法

 

在索引树结构中,有两种节点是我们经常接触的:分支节点branch和叶子节点leaf。当我们不断向叶子节点块插入数据,保持叶子节点有序性的同时,必然伴随着叶子节点分裂的过程。Oracle在处理叶子节点分裂问题的时候,是使用两种算法的。

 

我们假定一个叶子节点数据块已经装满,只要有一个新的数据值插入,索引叶子块就会进行分裂过程。索引叶子块在进行分裂的时候,是依据两种算法进行。

 

ü  9/1算法”:当新插入的数据值要大于(或者小于)所有叶子节点的索引列取值的时候。Oracle会单独为这个新插入的值分配出一个新的数据块,原有的数据叶子节点依然在原位上不变;

ü  5/5算法”:当新插入的数据索引列取值在叶子块最大和最小取值中间的时候,Oracle会应用不同的算法。以该值为份额,Oracle会将索引块叶子节点分别存放在两个块中,形成半满的结构;

 

两种算法分析下,我们可以得到这样的猜想。在“9/1算法”模式下,索引块是保持一个相对较满的状态,每次分裂实际上都是将新插入的取值单独保存在新索引块里面,而原有的叶子节点保持不变。

 

在“5/5算法”模式下,索引块会保持一个半满的状态。如果每次插入的都是中间值,那么所有的叶子节点块都是维持一个数据半满的状态。

 

那么,我们就得到推论:“9/1算法”模式下,叶子块中叶子节点保存很密实,使用空间相对高效。在“5/5算法”模式下,叶子块节点保存比较稀疏,占用空间较多。

 

下面,我们就通过一个实验来证明我们的猜想推论。

 

2、实验环境准备

 

我们选择Oracle 11gR2进行测试。

 

 

SQL> select * from v$version;

 

BANNER

--------------------------------------------------------------------------------

Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - Production

PL/SQL Release 11.2.0.1.0 - Production

CORE        11.2.0.1.0         Production

 

 

作为对比,我们要准备相同的索引列基础取值与数据行的数量。所以,我们需要构建相同的数据列结构。

 

 

SQL> create table t (id1 number, id2 number);

Table created

 

SQL> create index idx_t_id1 on t(id1);

Index created

 

SQL> create index idx_t_id2 on t(id2);

Index created

 

 

下面是本实验最困难的部分,为了实现对比,我们可以对id1列插入1…n的顺序序列值。如果我们对算法的阐述是正确的,那么每次进行叶子节点分裂的时候,都会遵从“9/1算法”。

 

难点在于id2,如何让每次插入的取值在1…n的范围中,而且是依次逼近中间取值的呢?笔者编写了如下代码。

 

 

set serveroutput on size 10000;

declare

   i number;

   a number;

   val number;

begin

  

   a := 1;

   for i in 1.. 100000 loop

     

      if (i mod 2 = 0) then

         --偶数

         val := a;

         a := a + 1;

      else

         --奇数

         val := 100000 + 1 - a;

      end if;

     

      insert into t values (i, val);

     

      if (i mod 1000 = 0) then

         dbms_output.put_line('Processing : '||to_char(i));

         commit;

      end if;

      dbms_output.put_line(to_char(i)||'--'||to_char(val));

   end loop;

end;

/

 

 

代码中的val,就是进行依次逼近的过程。为了进行演示,笔者选择n=10的时候,插入序列如下:

 

 

SQL>

 

1--10

2--1

3--9

4--2

5--8

6--3

7--7

8--4

9--6

10--5

 

PL/SQL procedure successfully completed

 

 

Val的每一个取值,都是向中心进行的插入过程。

 

3、实验过程结果

 

我们选择插入10万条记录之后,查看两个索引段的信息。

 

 

SQL> select segment_name, bytes, blocks, extents from dba_segments where wner='SYS' and segment_name in ('IDX_T_ID1','IDX_T_ID2');

 

SEGMENT_NAME              BYTES     BLOCKS    EXTENTS

-------------------- ---------- ---------- ----------

IDX_T_ID1               2097152        256         17

IDX_T_ID2               4194304        512         19

 

 

应该说,效果出乎意外的好。依次插入的索引维持了一个相对小的索引段结构。而“5/5算法”插入的索引对应的数据段较大。

 

由于叶子节点个数、大小均相同。我们不难得出,idx_t_id2的结构叶子节点序列较为稀疏。而idx_t_id1结构较为实密。

 

 

4rebuild重构

 

如果此时,我们进行rebuild重构的话,两个结构会如何呢?

 

 

SQL> alter index IDX_T_ID2 rebuild;

 

Index altered

 

SQL> alter index IDX_T_ID1 rebuild;

 

Index altered

 

SQL> select segment_name, bytes, blocks, extents from dba_segments where wner='SYS' and segment_name in ('IDX_T_ID1','IDX_T_ID2');

 

SEGMENT_NAME              BYTES     BLOCKS    EXTENTS

-------------------- ---------- ---------- ----------

IDX_T_ID1               2097152        256         17

IDX_T_ID2               2097152        256         17

 

 

rebuild之后,两个索引段维持了紧密结构。Id1列索引没有什么大变化,而id2变小。

 

进而,笔者有这样的猜测:在进行rebuild的过程中,Oracle会不会是将所有的列值获取到,排序之后进行成树过程,这样形成的过程是遵照“9/1算法”,比较紧密。

 

5、结论

 

本篇从宏观角度讨论了索引成树过程中叶子节点的分裂问题。从笔者的角度看,Oracle的两种算法是一种优化过的思路。如果数据依次递增或者递减添加,Oracle会认为你插入中值,引发索引叶子块分裂的概率较低,所以就维持一个较为紧密的索引叶子结构。

 

但是当我们插入是无规律的,始终在数据范围内进行插入。Oracle认为应该避免频繁的叶子节点分裂过程,所以维持了一个相对稀疏的叶子节点序列。这样也是一种优化过程。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/17203031/viewspace-734993/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
求道~

注册时间:2010-11-30

  • 博文量
    545
  • 访问量
    7544447