10g中构建“高”索引
[English]
作者：
fuyuncat
来源：
www.HelloDBA.com
分享到
索引的高度(Btree Level)是影响索引的性能的因素之一，高度的增加，意味着对索引的读的次数的增加。如果索引高度要增加，其必要条件就是左枝或右枝饱和。
枝节点中左节点是个特殊的节点，它是枝节点数据块中唯一小于该枝节点键值的节点，其指针并不在枝节点的数据区，而是在枝节点数据块的头部，并且它没有记录所指向节点的键值，而只有一个指针，并且每个枝节点都必须有一个左节点。对于右节点，因为索引长度是受限制的（和数据块大小相关），保证了一个节点中最少能放入一个键值。这2个特性决定了一个枝节点最少可以指向2个下一层节点。因此，即使索引键值数据足够大，要构建一颗高度为N的树也需要2^(n-1)条数据，最终的索引节点块为2^n-1块。例如，在一个块大小为2K的表空间中构建一个24层的索引，将需要32G的索引空间。
然而，在9i中，B树的左增长在算法上有缺陷：分裂时，如果枝节点已经饱和，则枝节点立即分裂。这样的话，在左分裂时，如果左枝上的所有枝节点已经全部饱和，即使右枝节点没有任何键值指针，也会造成左枝的“多米诺”式的分裂，造成树的高度增加（因为每个枝节点必须有一个左节点，因此右分裂不会造成这种情况）。利用这一缺陷，Jonathan Lewis只用24条数据就构建了一个24层高度的B树。
在10g中，这一缺陷已经被修正了：左枝节点饱和时，会先看其同父节点的右枝节点上是否有索引键数据（即是否存在指向右边的指针），如果没有，则将左枝节点上的数据转移到右枝节点，从而释放左枝节点的空间。
那是不是在10g中，如果需要构建一颗“高”数，就必须要如此大的空间呢？实际上，我们还可以利用右分裂的一个规则生成一个size很小但层数很高的索引：右分裂时，只要右枝节点是饱和就会分裂，而没有考虑对应的左枝节点上是否存在键值数据。利用这一规则，我们在构造出右枝的第一节点后，就将左枝上的右边数据删除，从而保证索引只占用少量数据。不过这一方法还是需要大量的中间数据。以下代码中，实际生成的表（HWM）、索引不足1M。
还有一点就是，节点数据块为空后，会被放到freelist的头部去，当索引分裂需要新数据块时，会先从freelist的头部先取出数据块进行分配，因此这就是我们以下代码能始终保证索引的size很小的原因。
注意：下面代码不要在生产环境上运行，运行前建议关闭Archive模式。
SQL代码
- 13:51:02 HELLODBA.COM> conn demo/demo
- Connected.
- 13:51:08 HELLODBA.COM> create table idx_split (a number, b varchar2(1446), c date) nologging pctfree 0;
- Table created.
- 13:51:20 HELLODBA.COM> create index idx_split_idx on idx_split (b, a) tablespace idx_2k nologging pctfree 10;
- Index created.
- 13:51:20 HELLODBA.COM> select object_id from user_objects where object_name='IDX_SPLIT_IDX';
- OBJECT_ID
- ----------
- 126371
- 13:52:00 HELLODBA.COM> conn demo/demo
- Connected.
- 13:52:21 HELLODBA.COM> set serveroutput on
- 13:52:21 HELLODBA.COM> set time on
- 13:52:21 HELLODBA.COM> truncate table idx_split;
- Table truncated.
- 13:52:21 HELLODBA.COM> declare
- 13:52:21 2 v_level number;
- 13:52:21 3 v_start number;
- 13:52:21 4 procedure build_tree( p_bl in number, p_rt in number, p_lst in number)
- 13:52:21 5 as
- 13:52:21 6 pragma autonomous_transaction;
- 13:52:21 7 v_rt number;
- 13:52:21 8 v_lst number;
- 13:52:21 9 begin
- 13:52:21 10 v_lst := p_lst;
- 13:52:21 11 v_rt := p_rt;
- 13:52:21 12 if (p_bl<=1) then
- 13:52:21 13 if v_rt > v_lst then
- 13:52:21 14 insert /*+append*/ into idx_split (a, b, c) values (v_rt, lpad('0',1446,'0'), sysdate);
- 13:52:21 15 --dbms_output.put_line('insert - '||(v_rt));
- 13:52:21 16 v_lst := v_rt;
- 13:52:21 17 commit;
- 13:52:21 18 end if;
- 13:52:21 19 return;
- 13:52:21 20 end if;
- 13:52:21 21 -- build the left tree
- 13:52:21 22 build_tree(p_bl-1, v_rt, v_lst);
- 13:52:21 23 v_rt := v_rt + power(2, p_bl-1)-power(2, p_bl-2);
- 13:52:21 24 if (p_bl > 3) then
- 13:52:21 25 if (v_rt > v_lst) then
- 13:52:21 26 insert /*+append*/ into idx_split (a, b, c) values (v_rt, lpad('0',1446,'0'), sysdate);
- 13:52:21 27 --dbms_output.put_line('insert - '||(v_rt));
- 13:52:21 28 v_lst := v_rt;
- 13:52:21 29 v_rt := v_rt + 1;
- 13:52:21 30 commit;
- 13:52:21 31 end if;
- 13:52:21 32 delete from idx_split where a between p_rt+1 and p_rt+power(2, p_bl-2)-1;
- 13:52:21 33 --dbms_output.put_line('delete - '||(p_rt+1)||' ~ '||(p_rt+power(2, p_bl-2)-1));
- 13:52:21 34 commit;
- 13:52:21 35 end if;
- 13:52:21 36 -- build the right tree
- 13:52:21 37 build_tree(p_bl-1, p_rt + power(2, p_bl-1)-power(2, p_bl-2), v_lst);
- 13:52:21 38 --execute immediate 'alter index idx_split_idx shrink space compact';
- 13:52:21 39 dbms_output.put_line('level - '||p_bl);
- 13:52:21 40 end;
- 13:52:21 41 begin
- 13:52:21 42 v_level := 24;
- 13:52:21 43 v_start := 1;
- 13:52:21 44 build_tree(v_level, 1, 0);
- 13:52:21 45 insert /*+append*/ into idx_split (a, b, c) values (power(2, v_level-1) + 1, lpad('0',1446,'0'), sysdate);
- 13:52:21 46 delete from idx_split where a between 2 and power(2, v_level-1);
- 13:52:21 47 dbms_output.put_line('deleted - '||SQL%ROWCOUNT||' rows.');
- 13:52:21 48 commit;
- 13:52:21 49 insert /*+append*/ into idx_split (a, b, c) values (power(2, v_level-1) + 2, lpad('0',1446,'0'), sysdate);
- 13:52:21 50 end;
- 13:52:21 51 /
达到索引高度限制（24）后 ，以上代码抛出了600错误。
SQL代码
- ORA-00600: internal error code, arguments: [6051], [], [], [], [], [], [], []
以上代码在PC server上运行了5个小时，表和索引的高水位都不足1M：
SQL代码
- HELLODBA.COM> select segment_name, bytes/1024/1024 "size(M)" from user_segments where segment_name like 'IDX_SPLIT%';
- SEGMENT_NAME size(M)
- ------------------ ----------
- IDX_SPLIT .125
- IDX_SPLIT_IDX .75
- HELLODBA.COM> validate index IDX_SPLIT_IDX;
- Index analyzed.
- HELLODBA.COM> select NAME, HEIGHT, BLOCKS, BR_BLKS, LF_BLKS from index_stats;
- NAME HEIGHT BLOCKS BR_BLKS LF_BLKS
- --------------- ---------- --------- ---------- ----------
- IDX_SPLIT_IDX 24 384 294 27
值得注意的是，在OLTP系统中，因为会对表进行大量的增、删、改，难免会出现上述情况——右（左）增长时，左（右）枝存在很大空闲，造成这样的现象：数据量很少，但索引树的高度却很高。
--- Fuyuncat Mark ---