HelloDBA [English]
搜索Internet 搜索 HelloDBABA
  Oracle技术站。email: fuyuncat@gmail.com  MSN: fuyuncat@hotmail.com   acoug  acoug 

10g中构建“高”索引

[English]

作者: fuyuncat

来源: www.HelloDBA.com

日期: 2009-10-07 01:52:02

分享到  新浪微博 腾讯微博 人人网 i贴吧 开心网 豆瓣 淘宝 推特 Facebook GMail Blogger Orkut Google Bookmarks

  索引的高度(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代码
  1. 13:51:02 HELLODBA.COM> conn demo/demo   
  2. Connected.   
  3. 13:51:08 HELLODBA.COM> create table idx_split (a number, b varchar2(1446), c date) nologging pctfree 0;   
  4.   
  5. Table created.   
  6.   
  7. 13:51:20 HELLODBA.COM> create index idx_split_idx on idx_split (b, a) tablespace idx_2k nologging pctfree 10;   
  8.   
  9. Index created.   
  10.   
  11. 13:51:20 HELLODBA.COM> select object_id from user_objects where object_name='IDX_SPLIT_IDX';   
  12.   
  13.  OBJECT_ID   
  14. ----------   
  15.     126371   
  16.   
  17. 13:52:00 HELLODBA.COM> conn demo/demo   
  18. Connected.   
  19. 13:52:21 HELLODBA.COM> set serveroutput on  
  20. 13:52:21 HELLODBA.COM> set time on  
  21. 13:52:21 HELLODBA.COM> truncate table idx_split;   
  22.   
  23. Table truncated.   
  24.   
  25. 13:52:21 HELLODBA.COM> declare  
  26. 13:52:21   2    v_level number;   
  27. 13:52:21   3    v_start number;   
  28. 13:52:21   4    procedure build_tree( p_bl in number, p_rt in number, p_lst in number)   
  29. 13:52:21   5    as  
  30. 13:52:21   6      pragma autonomous_transaction;   
  31. 13:52:21   7      v_rt number;   
  32. 13:52:21   8      v_lst number;   
  33. 13:52:21   9    begin  
  34. 13:52:21  10      v_lst := p_lst;   
  35. 13:52:21  11      v_rt := p_rt;   
  36. 13:52:21  12      if (p_bl<=1) then  
  37. 13:52:21  13        if  v_rt > v_lst then  
  38. 13:52:21  14          insert /*+append*/ into idx_split (a, b, c) values (v_rt, lpad('0',1446,'0'), sysdate);   
  39. 13:52:21  15          --dbms_output.put_line('insert - '||(v_rt));   
  40. 13:52:21  16          v_lst := v_rt;   
  41. 13:52:21  17          commit;   
  42. 13:52:21  18        end if;   
  43. 13:52:21  19        return;   
  44. 13:52:21  20      end if;   
  45. 13:52:21  21      -- build the left tree   
  46. 13:52:21  22      build_tree(p_bl-1, v_rt, v_lst);   
  47. 13:52:21  23      v_rt := v_rt + power(2, p_bl-1)-power(2, p_bl-2);   
  48. 13:52:21  24      if (p_bl > 3) then  
  49. 13:52:21  25        if (v_rt > v_lst) then  
  50. 13:52:21  26          insert /*+append*/ into idx_split (a, b, c) values (v_rt, lpad('0',1446,'0'), sysdate);   
  51. 13:52:21  27          --dbms_output.put_line('insert - '||(v_rt));   
  52. 13:52:21  28          v_lst := v_rt;   
  53. 13:52:21  29          v_rt := v_rt + 1;   
  54. 13:52:21  30          commit;   
  55. 13:52:21  31        end if;   
  56. 13:52:21  32        delete from idx_split where a between p_rt+1 and p_rt+power(2, p_bl-2)-1;   
  57. 13:52:21  33        --dbms_output.put_line('delete - '||(p_rt+1)||' ~ '||(p_rt+power(2, p_bl-2)-1));   
  58. 13:52:21  34        commit;   
  59. 13:52:21  35      end if;   
  60. 13:52:21  36      -- build the right tree   
  61. 13:52:21  37      build_tree(p_bl-1, p_rt + power(2, p_bl-1)-power(2, p_bl-2), v_lst);   
  62. 13:52:21  38      --execute immediate 'alter index idx_split_idx shrink space compact';   
  63. 13:52:21  39      dbms_output.put_line('level - '||p_bl);   
  64. 13:52:21  40    end;   
  65. 13:52:21  41  begin  
  66. 13:52:21  42    v_level := 24;   
  67. 13:52:21  43    v_start := 1;   
  68. 13:52:21  44    build_tree(v_level, 1, 0);   
  69. 13:52:21  45    insert /*+append*/ into idx_split (a, b, c) values (power(2, v_level-1) + 1, lpad('0',1446,'0'), sysdate);   
  70. 13:52:21  46    delete from idx_split where a between 2 and power(2, v_level-1);   
  71. 13:52:21  47    dbms_output.put_line('deleted - '||SQL%ROWCOUNT||' rows.');   
  72. 13:52:21  48    commit;   
  73. 13:52:21  49    insert /*+append*/ into idx_split (a, b, c) values (power(2, v_level-1) + 2, lpad('0',1446,'0'), sysdate);   
  74. 13:52:21  50  end;   
  75. 13:52:21  51  /  

  达到索引高度限制(24)后 ,以上代码抛出了600错误。

SQL代码
  1. ORA-00600: internal error code, arguments: [6051], [], [], [], [], [], [], []  

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

SQL代码
  1. HELLODBA.COM> select segment_name, bytes/1024/1024 "size(M)" from user_segments where segment_name like 'IDX_SPLIT%';   
  2.   
  3. SEGMENT_NAME       size(M)   
  4. ------------------ ----------   
  5. IDX_SPLIT          .125   
  6. IDX_SPLIT_IDX      .75   
  7.   
  8. HELLODBA.COM> validate index IDX_SPLIT_IDX;   
  9.   
  10. Index analyzed.   
  11.   
  12. HELLODBA.COM> select NAME, HEIGHT, BLOCKS, BR_BLKS, LF_BLKS from index_stats;   
  13.   
  14. NAME            HEIGHT     BLOCKS    BR_BLKS    LF_BLKS   
  15. --------------- ---------- --------- ---------- ----------   
  16. IDX_SPLIT_IDX   24         384       294        27   

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

    --- Fuyuncat Mark ---

Top

Copyright ©2005,HelloDBA.Com 保留一切权利

申明
by fuyuncat