查看: 41953|回复: 72

[精华] 关于索引(index)的中度理解,请指正!

[复制链接]
招聘 : 数据库管理员
论坛徽章:
21
授权会员
日期:2005-10-30 17:05:332012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:36马上有车
日期:2014-02-19 11:55:14马上有房
日期:2014-02-19 11:55:14马上有钱
日期:2014-02-19 11:55:14马上有对象
日期:2014-02-19 11:55:142012新春纪念徽章
日期:2012-02-13 15:11:36
发表于 2004-6-30 12:48 | 显示全部楼层 |阅读模式
本文主要侧重于索引的物理结构,探究了:
1)索引的root,branch,leaf;
2)索引的分裂;
3)索引的重用;
招聘 : 数据库管理员
论坛徽章:
21
授权会员
日期:2005-10-30 17:05:332012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:36马上有车
日期:2014-02-19 11:55:14马上有房
日期:2014-02-19 11:55:14马上有钱
日期:2014-02-19 11:55:14马上有对象
日期:2014-02-19 11:55:142012新春纪念徽章
日期:2012-02-13 15:11:36
 楼主| 发表于 2004-6-30 12:49 | 显示全部楼层
1)索引的root,branch,leaf;

~~~Leaf~~~

[php]
SQL> create table t(x char(1024));

Table created.

SQL> create index ti on t(x);

Index created.

SQL> insert into t values(1);

1 row created.

SQL> commit;

Commit complete.

SQL> select file_id,extent_id,block_id,blocks from dba_extents where segment_name='TI';

   FILE_ID  EXTENT_ID   BLOCK_ID     BLOCKS
---------- ---------- ---------- ----------
         3          0        249          8

'BLOCK 250 开始存储索引的第一个leaf note'

SQL> alter system dump datafile 3 block 250;

System altered.
[/php]
'trace...'
kdxledsz 0
kdxlebksz 8036
row#0[7001] flag: -----, lock: 2
col 0; len 1024; (1024):  'indexed data value(1024B),第一个31代表1'
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
......
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 1; len 6; (6):  00 c0 00 da 00 00  'RowID(6B)'
----- end of leaf block dump -----

index leaf note每个entry有5列:
row header(3B)|length(1B)|indexed data value(1024B)|length(1B)|RowID(6B)
这样每个row的大小为:3+1+1024+1+6=1035
db_block_size=8192,
block的默认pct_free=10%,
所以每个block能存储7个rows:
[php]
SQL> select 8192*0.9/1035 from dual;

8192*0.9/1035
-------------
   7.12347826

'再插入6row的数据:'

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

PL/SQL procedure successfully completed.

SQL> commit;

Commit complete.

SQL> ANALYZE INDEX TI VALIDATE STRUCTURE;

Index analyzed.

SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks from index_stats;

BTREE_SPACE USED_SPACE   PCT_USED     BLOCKS    LF_BLKS    BR_BLKS
----------- ---------- ---------- ---------- ---------- ----------
       8000       7259         91          8          1          0        '只有一个leaf note,没有branch note'

SQL> alter system dump datafile 3 block 250;

System altered.
[/php]
'trace...'
kdxlebksz 8036
row#0[7001] flag: -----, lock: 0
col 0; len 1024; (1024): '31代表1'
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
col 1; len 6; (6):  00 c0 00 da 00 00
row#1[5966] flag: -----, lock: 2
col 0; len 1024; (1024): '32代表2'
32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
...
row#6[791] flag: -----, lock: 2
col 0; len 1024; (1024): '37代表7'
37 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 1; len 6; (6):  00 c0 00 da 00 06
----- end of leaf block dump -----

使用道具 举报

回复
招聘 : 数据库管理员
论坛徽章:
21
授权会员
日期:2005-10-30 17:05:332012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:36马上有车
日期:2014-02-19 11:55:14马上有房
日期:2014-02-19 11:55:14马上有钱
日期:2014-02-19 11:55:14马上有对象
日期:2014-02-19 11:55:142012新春纪念徽章
日期:2012-02-13 15:11:36
 楼主| 发表于 2004-6-30 12:50 | 显示全部楼层
~~Branch and Root~~

看看插入第8条数据后,会怎么样?
[php]
SQL> insert into t values(8);

1 row created.

SQL> commit;

Commit complete.

SQL> ANALYZE INDEX TI VALIDATE STRUCTURE;

Index analyzed.

SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks from index_stats;

BTREE_SPACE USED_SPACE   PCT_USED     BLOCKS    LF_BLKS    BR_BLKS
----------- ---------- ---------- ---------- ---------- ----------
      24032       8305         35          8          2          1
[/php]
发现BTREE_SPACE=3个blocks的大小了,并且有2个leaf notes;1个branch,也就是root,单独占一个block;
因为两个leaf notes不能只是傻乎乎的排列在那里,必须有上一层的branch(root) note管理他们;
并且你会发现,这个root占用的block是最开始的那个leaf占用的block 250;
而将那个leaf 中的entries转移到后面的block(251)中去了;
同时插入的第8行数据,放在了新的block中(252);
为什么将第一个leaf转移到后面的block,而将这个block作为root,是因为root的信息保存在数据字典中,若修改数据字典的代价要会更大一些。

看看trace,证实上面的说法:
[php]
SQL> alter system dump datafile 3 block 250;  'root'

System altered.
[/php]
'trace..
注意:
brach中的每个entry有2个columns:
一个是他的child block中的最大值,另一个是他下一层block的address'
kdxbrbksz 8060
row#0[8053] dba: 12583164=0xc000fc
col 0; len 1; (1):  38  '38代表8,即最大值'
col 1; TERM
----- end of branch block dump -----
End dump data blocks tsn: 8 file#: 3 minblk 250 maxblk 250

[php]
SQL> alter system dump datafile 3 block 251;

System altered.
[/php]
'trace..发现row的顺序没有变,但是物理偏移量正好和原来相反了791~7001'
...
row#0['791'] flag: -----, lock: 0
col 0; len 1024; (1024):
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
col 1; len 6; (6):  00 c0 00 da 00 00
row#1[1826] flag: -----, lock: 0
col 0; len 1024; (1024):
32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
...
row#6['7001'] flag: -----, lock: 0
col 0; len 1024; (1024):
37 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
col 1; len 6; (6):  00 c0 00 da 00 06
----- end of leaf block dump -----

[php]
SQL>  alter system dump datafile 3 block 252;

System altered.
[/php]
'trace..'
row#0[7001] flag: -----, lock: 0
col 0; len 1024; (1024): '38代表8'
38 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...

使用道具 举报

回复
招聘 : 数据库管理员
论坛徽章:
21
授权会员
日期:2005-10-30 17:05:332012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:36马上有车
日期:2014-02-19 11:55:14马上有房
日期:2014-02-19 11:55:14马上有钱
日期:2014-02-19 11:55:14马上有对象
日期:2014-02-19 11:55:142012新春纪念徽章
日期:2012-02-13 15:11:36
 楼主| 发表于 2004-6-30 12:50 | 显示全部楼层
2)索引的分裂;

如果一个leaf block已经满了(例如block 251),此时又产生了新的entry,按照他的value应该插入到block 251当中;
此时251中的值是:1,2,3,4,5,6,7
因为是char数据类型,如果再插入51,按照char的排序,51应该插入到5之后6之前;
这种情况下,会将block 251中的内容分裂成两部分,低于51的部分保留,高于51的部分到一个新的block中去。
这样的话,应该是:
block 250:root
block 251:1,2,3,4,5,51
block 252:8
block 253:6,7
[php]
SQL> insert into t values(51);

1 row created.

SQL> commit;

Commit complete.

SQL> ANALYZE INDEX TI VALIDATE STRUCTURE;

Index analyzed.

SQL> select btree_space,used_space,pct_used,blocks,lf_blks,br_blks from index_stats;

BTREE_SPACE USED_SPACE   PCT_USED     BLOCKS    LF_BLKS    BR_BLKS
----------- ---------- ---------- ---------- ---------- ----------
      32032       9351         30          8          3          1   '4个blocks,1个root,3个leaf'

SQL> alter system dump datafile 3 block 251;

System altered.
[/php]
'trace..'
row#0[1826] flag: -----, lock: 0
col 0; len 1024; (1024): '31代表1'
31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
...
row#4[5966] flag: -----, lock: 0
col 0; len 1024; (1024): '35代表5'
35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#5[7001] flag: -----, lock: 2
col 0; len 1024; (1024): '35代表5,31代表1,这个值应该是51'
35 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
[php]
SQL> alter system dump datafile 3 block 253;

System altered.
[/php]
'trace..'
row#0[5966] flag: -----, lock: 0
col 0; len 1024; (1024): '36代表6'
36 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#1[7001] flag: -----, lock: 0
col 0; len 1024; (1024): '37代表7'
37 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
......
col 1; len 6; (6):  00 c0 00 da 00 06
----- end of leaf block dump -----

使用道具 举报

回复
招聘 : 数据库管理员
论坛徽章:
21
授权会员
日期:2005-10-30 17:05:332012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:36马上有车
日期:2014-02-19 11:55:14马上有房
日期:2014-02-19 11:55:14马上有钱
日期:2014-02-19 11:55:14马上有对象
日期:2014-02-19 11:55:142012新春纪念徽章
日期:2012-02-13 15:11:36
 楼主| 发表于 2004-6-30 12:51 | 显示全部楼层
3)索引的重用;

我的理解:索引是按照value对row进行排序的。所谓重用,是对row 的重用,而不是对row所在物理存储的重用。
有新的row被插入,首先按照value排序,将他放在合适的row list中(?),如果他的位置正好原来有个row被删掉了,则重用这个row;
但是物理存储是依次(或随意?)向下开辟的。
看这个例子,删除4,插入31,31重用了原来4在row list中的位置,但是物理存储是新开辟的:
[php]
SQL> delete from t where x=4;

1 row deleted.

SQL> commit;

Commit complete.

SQL> alter system dump datafile 3 block 251;

System altered.
[/php]
'trace..'
row#3[4931] flag: ---D-, lock: 2 '---D-代表被删掉'
col 0; len 1024; (1024):
34 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
[php]
SQL> insert into t values(31);

1 row created.

SQL> commit;

Commit complete.

SQL> alter system dump datafile 3 block 251;

System altered.
[/php]
'trace..'
row#1[2861] flag: -----, lock: 0
col 0; len 1024; (1024): '2'
32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#2[3896] flag: -----, lock: 0
col 0; len 1024; (1024): '3'
33 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
...
row#3['791'] flag: -----, lock: 2
col 0; len 1024; (1024): '31,重用了原来4在row list 中的位置,但是物理存储是新的791,原来是4931'
33 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
row#4[5966] flag: -----, lock: 0
col 0; len 1024; (1024): '5'
35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

使用道具 举报

回复
论坛徽章:
86
ITPUB元老
日期:2005-02-28 12:57:002012新春纪念徽章
日期:2012-01-04 11:49:542012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:20咸鸭蛋
日期:2012-05-08 10:27:19版主8段
日期:2012-05-15 15:24:112013年新春福章
日期:2013-02-25 14:51:24
发表于 2004-6-30 13:29 | 显示全部楼层

可参考

http://www.itpub.net/showthread. ... 768&pagenumber=

关于索引叶子节点的分裂,要注意的是,最右边的 block  分裂的时候,只放 10%的数据进最右边的 block,这是合理的,比如顺序增长类型的数字,总不能 5-5 分裂的

fcp2084@OCN> select * from v$sysstat where name like '%split%';

STATISTIC# NAME                                                                  CLASS      VALUE
---------- ---------------------------------------------------------------- ---------- ----------
       195 leaf node splits                                                        128        412
       196 leaf node 90-10 splits                                                  128         40
       197 branch node splits                                                      128          1


另: 在索引的每一个层次之间,每一个层最左边的节点的block头部都有一个 指向下层最左边的块的指针,这样有利于 fast  full  scan 的快速定位最左边的叶子节点

使用道具 举报

回复
招聘 : 数据库管理员
论坛徽章:
21
授权会员
日期:2005-10-30 17:05:332012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:36马上有车
日期:2014-02-19 11:55:14马上有房
日期:2014-02-19 11:55:14马上有钱
日期:2014-02-19 11:55:14马上有对象
日期:2014-02-19 11:55:142012新春纪念徽章
日期:2012-02-13 15:11:36
 楼主| 发表于 2004-6-30 13:50 | 显示全部楼层
对于索引的平衡,一个问题:
索引的平衡是指,所有叶子中数据到root节点的距离,B tree索引是永远不会打破这种平衡的。
也就是说所有的叶子节点必定在最底层的BLEVEL中。
理解的对吗?

使用道具 举报

回复
论坛徽章:
86
ITPUB元老
日期:2005-02-28 12:57:002012新春纪念徽章
日期:2012-01-04 11:49:542012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:202012新春纪念徽章
日期:2012-02-13 15:13:20咸鸭蛋
日期:2012-05-08 10:27:19版主8段
日期:2012-05-15 15:24:112013年新春福章
日期:2013-02-25 14:51:24
发表于 2004-6-30 14:16 | 显示全部楼层
那当然!

看来你还没有完全理解 索引的树是怎么变化的
当任意一个层次的节点撑满之后,不是往下扩展 子节点,而是分裂,这样将可能增加上层节点的记录

随着记录的增多,都是先 最底层的满,分裂--->上层满,分裂-----> ...  ------> root 满,分裂(不过这个时候分裂稍微在物理位置处理跟其他节点有区别,但逻辑上来说是一个意思),root满再分裂的时候,就是索引的 level 增加的时候,root 分裂的时候,所有其他节点自然高度都同步发生了变化


如果搭一个模型来解释这个问题,很清楚的

使用道具 举报

回复
招聘 : 数据库管理员
论坛徽章:
21
授权会员
日期:2005-10-30 17:05:332012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:362012新春纪念徽章
日期:2012-02-13 15:11:36马上有车
日期:2014-02-19 11:55:14马上有房
日期:2014-02-19 11:55:14马上有钱
日期:2014-02-19 11:55:14马上有对象
日期:2014-02-19 11:55:142012新春纪念徽章
日期:2012-02-13 15:11:36
 楼主| 发表于 2004-6-30 14:26 | 显示全部楼层
嗯,清楚了。
root满了时候的分裂与其他分裂不同的地方是不是这样:
将原来root转移到一个新的block中,而将这个block给新的root;这样做是因为root的信息保存在数据字典中,若修改数据字典的代价要会更大一些。

使用道具 举报

回复
论坛徽章:
8
授权会员
日期:2005-10-30 17:05:33会员2006贡献徽章
日期:2006-04-17 13:46:34会员2007贡献徽章
日期:2007-09-26 18:42:102011新春纪念徽章
日期:2011-02-18 11:42:49ITPUB 11周年纪念徽章
日期:2012-10-09 18:03:32兰博基尼
日期:2014-01-31 14:56:26优秀写手
日期:2015-01-08 06:00:14优秀写手
日期:2015-02-12 06:00:15
发表于 2004-6-30 16:34 | 显示全部楼层
不错

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

TOP技术积分榜 社区积分榜 徽章 团队 统计 知识索引树 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 
京ICP备09055130号-4  北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表