技术开发 频道

10g中构建"高"索引

  【IT168 技术文档】索引的高度(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模式。

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错误。 

ORA-00600: internal error code, arguments: [6051], [], [], [], [], [], [], []

  以上代码在PC server上运行了5个小时,表和索引的高水位都不足1M: 

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系统中,因为会对表进行大量的增、删、改,难免会出现上述情况——右(左)增长时,左(右)枝存在很大空闲,造成这样的现象:数据量很少,但索引树的高度却很高。

0
相关文章