ITPub博客

首页 > Linux操作系统 > Linux操作系统 > index branch and leaf block structure(转)

index branch and leaf block structure(转)

原创 Linux操作系统 作者:aaqwsh 时间:2011-03-12 11:20:34 0 删除 编辑

Index Range Scans

An index range scan is a common operation for accessing selective data. It can be bounded (bounded on both sides) or unbounded (on one or both sides). Data is returned in the ascending order of index columns.
Multiple rows with identical values are sorted in ascending order by rowid。

我以前也看过这段话,但是也就简单的过去了,没有细想过,所以当小霸王问为什么相同值会按照rowid排序的时候我也没给出特别明确的答复。做了以下实验,应该可以给小霸王
一个满意的答复了。

在考虑这个问题的时候我们首先要回顾的知识点是unique index和non-unique index它的构造是不一样
的。对于unique index,它的branch block里面只保存key value和leaf block的address,因为根据这
2个值就可以定位当新值插入时会选择哪个leaf block进行插入,leaf block里面的值也没必要按照rowid的顺序排列了,只需要按照key value排序就行了。但是如果是non-unique index,branch block
里面必须保存key value,leaf block的address,和rowid。在leaf block里面如果key value相同的话
要按照rowid做升序排列,我个人觉得这样做会有2个好处,一个是可以提高相同一个leaf block内相同key value能尽量关联到相同的data block。第2个好处是当插入新的相同key value时能很容易定位插入到哪个block。为了能做到这些,non-unique index必须在branch block里面放入rowid。下面来看一下实验。
首先我们需要创建一张测试表

SQL> create table test(a number);

Table created.

插入2000条数据,值为1到2000

SQL> begin                     
  2  for i in 1..2000 loop    
  3  insert into test values(i);
  4  end loop;                 
  5  commit;                   
  6  end;                      
  7  /                         

PL/SQL procedure successfully completed.
再插入500条值为500的数据,这样的话这个表存在501条值为500的记录

SQL> begin                     
  2  for i in 1..500 loop    
  3  insert into test values(500);
  4  end loop;                 
  5  commit;                   
  6  end;                      
  7  /                         

PL/SQL procedure successfully completed.                        
SQL>

创建一个non-unique index

SQL> create index ind_test on test(a);

Index created.

查看non-unique index的object_id

SQL> select object_id from dba_objects where object_name=’IND_TEST’;

 OBJECT_ID
———-
     54032

dump non-unique index的层级结构

SQL>  ALTER SESSION SET EVENTS ‘immediate trace name TREEDUMP level 54032′;

Session altered.

—– begin tree dump
branch: 0×1000044 16777284 (0: nrow: 6, level: 1)
   leaf: 0×1000045 16777285 (-1: nrow: 279 rrow: 279)
   leaf: 0×100004d 16777293 (0: nrow: 275 rrow: 275)
   leaf: 0×100004e 16777294 (1: nrow: 486 rrow: 486)
   leaf: 0×1000046 16777286 (2: nrow: 533 rrow: 533)
   leaf: 0×1000048 16777288 (3: nrow: 533 rrow: 533)
   leaf: 0×1000047 16777287 (4: nrow: 394 rrow: 394)
—– end tree dump

看一下branch block的所在文件和块号,准备dump

SQL> select dbms_utility.data_block_address_file(16777284) “file”,
  2  dbms_utility.data_block_address_block(16777284) “block” from dual;

      file      block
———- ———-
         4         68

dump branch block的实际内容

SQL> alter system dump datafile 4 block 68;

System altered.
分析一下branch block,可以看到leaf block是从kdxbrlmc 16777285这个地址开始
dba: 16777294这个块与其他块有点不同,它的col1保存的就是rowid 01 00 00 3e 00 4a
,这里的col0 c2 06转换成10进制的值就是500,为什么其他leaf block的col1都被置为
TERM省略掉了呢,因为只有16777293,16777294这两个块保存了500这个重复值,所以当继续
插入500时,oracle可以根据这边的col1来定位是插入到16777293还是插入到16777294。插入
其他值并不受这个影响,所以oracle对这个地方做了优化,并不是所有non-unique branch block
都是需要记录rowid的。

kdxbrlmc 16777285=0×1000045
kdxbrsno 1
kdxbrbksz 8056
kdxbr2urrc 0
row#0[8020] dba: 16777293=0×100004d
col 0; len 3; (3):  c2 03 51
col 1; TERM
row#1[8006] dba: 16777294=0×100004e
col 0; len 2; (2):  c2 06
col 1; len 6; (6):  01 00 00 3e 00 4a
row#2[8047] dba: 16777286=0×1000046
col 0; len 3; (3):  c2 06 2a
col 1; TERM
row#3[8038] dba: 16777288=0×1000048
col 0; len 3; (3):  c2 0b 4b
col 1; TERM
row#4[8029] dba: 16777287=0×1000047
col 0; len 3; (3):  c2 11 08   

再来看一下具体的leaf block,看看里面是不是按rowid的顺序排列的

SQL> select dbms_utility.data_block_address_file(16777294) “file”,                         
  2  dbms_utility.data_block_address_block(16777294) “block” from dual;

      file      block
———- ———-
         4         78

SQL> alter system dump datafile 4 block 78;

System altered.
可以看到,相同的key value它的顺序是根据rowid的升序排列的

kdxlenxt 16777286=0×1000046
kdxleprv 16777293=0×100004d
kdxledsz 0
kdxlebksz 8032
row#0[4656] flag: —-S-, lock: 2, len=12
col 0; len 2; (2):  c2 06
col 1; len 6; (6):  01 00 00 3e 00 4a
row#1[4668] flag: —-S-, lock: 2, len=12
col 0; len 2; (2):  c2 06
col 1; len 6; (6):  01 00 00 3e 00 4b
row#2[4680] flag: —-S-, lock: 2, len=12
col 0; len 2; (2):  c2 06
col 1; len 6; (6):  01 00 00 3e 00 4c
row#3[4692] flag: —-S-, lock: 2, len=12
col 0; len 2; (2):  c2 06
col 1; len 6; (6):  01 00 00 3e 00 4d
row#4[4704] flag: —-S-, lock: 2, len=12
col 0; len 2; (2):  c2 06
col 1; len 6; (6):  01 00 00 3e 00 4e
row#5[4716] flag: —-S-, lock: 2, len=12
再来看一下unique index是什么样的

SQL> drop index ind_test;

Index dropped.
SQL> truncate table test;

Table truncated.

SQL> begin                      
  2  for i in 1..2000 loop      
  3  insert into test values(i);
  4  end loop;                  
  5  commit;                    
  6  end;                       
  7  / 

PL/SQL procedure successfully completed.

SQL> create unique index ind_test on test(a);

Index created.
      
      
SQL> select object_id from dba_objects where object_name=’IND_TEST’;

 OBJECT_ID
———-
     54049

SQL> ALTER SESSION SET EVENTS ‘immediate trace name TREEDUMP level 54049′;

Session altered.

—– begin tree dump
branch: 0×1000044 16777284 (0: nrow: 4, level: 1)
   leaf: 0×1000045 16777285 (-1: nrow: 520 rrow: 520)
   leaf: 0×1000046 16777286 (0: nrow: 513 rrow: 513)
   leaf: 0×1000047 16777287 (1: nrow: 513 rrow: 513)
   leaf: 0×1000048 16777288 (2: nrow: 454 rrow: 454)
—– end tree dump

SQL> select dbms_utility.data_block_address_file(16777284) “file”,                         
  2  dbms_utility.data_block_address_block(16777284) “block” from dual;

      file      block
———- ———-
         4         68

SQL> alter system dump datafile 4 block 68;

System altered.
注意,unique index里面并没有col1这个值,也就说明unique index不保留rowid

kdxbrlmc 16777285=0×1000045
kdxbrsno 0
kdxbrbksz 8056
kdxbr2urrc 0
row#0[8048] dba: 16777286=0×1000046
col 0; len 3; (3):  c2 06 16
row#1[8040] dba: 16777287=0×1000047
col 0; len 3; (3):  c2 0b 23
row#2[8032] dba: 16777288=0×1000048
col 0; len 3; (3):  c2 10 30

SQL> select dbms_utility.data_block_address_file(16777286) “file”,                         
  2  dbms_utility.data_block_address_block(16777286) “block” from dual;

      file      block
———- ———-
         4         70

SQL> alter system dump datafile 4 block 70;

System altered.
可以看到,unique index是根据key value的值做升序排列的

kdxlenxt 16777287=0×1000047
kdxleprv 16777285=0×1000045
kdxledsz 6
kdxlebksz 8032
row#0[8020] flag: ——, lock: 0, len=12, data:(6):  01 00 00 3c 02 08
col 0; len 3; (3):  c2 06 16
row#1[8008] flag: ——, lock: 0, len=12, data:(6):  01 00 00 3c 02 09
col 0; len 3; (3):  c2 06 17
row#2[7996] flag: ——, lock: 0, len=12, data:(6):  01 00 00 3c 02 0a
col 0; len 3; (3):  c2 06 18
row#3[7984] flag: ——, lock: 0, len=12, data:(6):  01 00 00 3c 02 0b
col 0; len 3; (3):  c2 06 19
row#4[7972] flag: ——, lock: 0, len=12, data:(6):  01 00 00 3c 02 0c
col 0; len 3; (3):  c2 06 1a

Posted in Oracle at 4:49 下午 由 wanghai

本文简单讨论非唯一性与唯一性B*TREE索引在存储上的差异,以及全局索引及本地索引在存储上的差异。


一、唯一性索引与非唯一性索引
--建立表
SQL> create table k1(id int);

Table created

SQL> create table k2(id int);

Table created

--建立索引
SQL> create index idx_k1 on k1(id);

Index created

SQL> create unique index idx_k1 on k2(id);

Index created

--插入数据
SQL> insert into k1 values(1);

1 row inserted

SQL> insert into k2 values(1);

1 row inserted

SQL> commit;

Commit complete

--checkpoint,使数据刷新到硬盘上
SQL> alter system checkpoint;

--查看索引位置
SQL> select segment_name,file_id,block_id from dba_extents where segment_name in ('IDX_K1','IDX_K2');

SEGMENT_NAME FILE_ID BLOCK_ID
-------------------------------- ---------- ----------
IDX_K1 8 5457
IDX_K2 8 5465

--dump索引block
--一般来说,每一个segment的第一个block是segment header,它不存放用户数据,故我们一般从第二个block开始dump:
SQL> alter system dump datafile 8 block 5458;

System altered

SQL> alter system dump datafile 8 block 5466;

System altered

==============================================================================
普通索引IDX_K1:
row#0[8024] flag: -----, lock: 2
col 0; len 2; (2): c1 02 --这是ID列
col 1; len 6; (6): 02 00 15 42 00 00 --这列是rowid,它以一个列的形式存在在索引结构中

--注意:不要以为上面是两列的组合索引,最后一列其实是rowid。(如果是两列的组合非唯一性索引,这里会显示有三列的信息)
--实际上,非唯一性索引中,dump 索引块出来的信息的最后一列总是rowid。

唯一性索引IDX_K2:
row#0[8025] flag: -----, lock: 2, data:(6): 02 00 15 4a 00 00
^^^^^^^^^^^^^^^^^ 这是rowid,放在row header上
col 0; len 2; (2): c1 02 --这是索引当前键值

===============================================================================
从上面结果可以看出,每一个非唯一性索引entry比唯一性索引多出rowid部分。


二、全局索引与本地索引

--创建表和索引
SQL> CREATE TABLE PAR1(ID INT) PARTITION BY RANGE(ID)
2 (PARTITION P1 VALUES LESS THAN(10))
3 ;

Table created


SQL> CREATE TABLE PAR2(ID INT) PARTITION BY RANGE(ID)
2 (PARTITION P1 VALUES LESS THAN(10))

Table created

SQL> CREATE TABLE PAR3(ID INT) PARTITION BY RANGE(ID)
2 (PARTITION P1 VALUES LESS THAN(10))
3 ;

Table created

SQL> CREATE UNIQUE INDEX GIDX_PAR1 ON PAR1(ID);

Index created

SQL> CREATE INDEX GIDX_PAR2 ON PAR2(ID);

Index created

SQL> CREATE INDEX LIDX_PAR3 ON PAR3(ID) LOCAL;

Index created

--插入数据
SQL> INSERT INTO PAR1 VALUES(1);

1 row inserted

SQL> INSERT INTO PAR2 VALUES(1);

1 row inserted

SQL> INSERT INTO PAR3 VALUES(1);

1 row inserted

SQL> COMMIT;

Commit complete

--刷新数据到硬盘
SQL> ALTER SYSTEM CHECKPOINT;

System altered

--索引的存储位置
SQL> select segment_name,file_id,block_id from dba_extents where segment_name in ('GIDX_PAR1','GIDX_PAR2','LIDX_PAR3');

SEGMENT_NAME FILE_ID BLOCK_ID
-------------------------------- ---------- ----------
GIDX_PAR2 9 1553
GIDX_PAR1 9 1561
LIDX_PAR3 9 1577


--dump索引
SQL> ALTER SYSTEM DUMP DATAFILE 9 BLOCK 1562;

System altered

SQL> ALTER SYSTEM DUMP DATAFILE 9 BLOCK 1554;

System altered

SQL> ALTER SYSTEM DUMP DATAFILE 9 BLOCK 1578;

System altered

=============================索引的存储情况==============================
索引GIDX_PAR1:全局唯一性索引
row#0[8021] flag: -----, lock: 2, data:(10): 00 00 1f 5a 02 00 15 82 00 00
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^rowid,注意长度是10
col 0; len 2; (2): c1 02

索引GIDX_PAR2:全局非唯一性索引
row#0[8020] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 10; (10): 00 00 1f 5c 02 40 06 0a 00 00
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^rowid,长度是10

索引LIDX_PAR3:本地索引
row#0[8024] flag: -----, lock: 2
col 0; len 2; (2): c1 02
col 1; len 6; (6): 02 40 06 22 00 00
^^^^^^^^^^^^^^^^^rowid,长度是6
========================================================================

总结:
1、非唯一性索引中,每一个index entry都包含有当前的键值及rowid两个部分。
dump block显示的index entry信息中的最后一列就是rowid。
2、唯一性索引中,index entry只包含当前的键值信息。rowid会在row header存放。
3、普通索引每一个entry的长度是6个字节
全局索引的每一个entry的长度是10个字节
4、全局索引比普通索引每一个entry多存放了OBJECT_ID的信息。
5、如果可以建立唯一性索引,就不要建普通索引。唯一性索引比一般索引占用空间要少。
 
作者 space6212 00:40 <!-- comment these out if you want to see an example of custom fields, but remember to name the fields in the same way they are named here: 'imfeeling' (livejournal.com style), 'listening' and 'new_field'

: ?

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

上一篇: ORACLE坏块总结2
请登录后发表评论 登录
全部评论

注册时间:2010-11-24

  • 博文量
    132
  • 访问量
    262299