ITPUB论坛－专业的IT技术社区

登录 注册
ITPUB论坛－专业的IT技术社区»论坛 › ≡ 大数据与数据库 ≡ › Oracle专题深入讨论 › B*Tree索引能有多高?--推荐Jonathan Lewis 的一篇经典文 ...
123下一页
返回列表 发新帖
楼主: eygle
收藏 | 打印 上一主题 下一主题

B*Tree索引能有多高?--推荐Jonathan Lewis 的一篇经典文章

[复制链接]
liyongdong
论坛徽章:
62
2015中国数据库技术大会纪念徽章 日期:2015-04-24 16:04:24版主2段 日期:2012-05-15 15:24:112012新春纪念徽章 日期: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:202012新春纪念徽章 日期:2012-01-04 11:49:54ITPUB十周年纪念徽章 日期:2011-11-01 16:19:41现任管理团队成员 日期:2011-05-07 01:45:08
11#
发表于 2005-3-1 11:49 | 只看该作者
好

使用道具 举报

回复
hooman
论坛徽章:
2
ITPUB元老 日期:2005-03-02 12:45:52授权会员 日期:2005-10-30 17:05:33
12#
发表于 2005-3-1 12:52 | 只看该作者

Re: B*Tree索引能有多高?--推荐Jonathan Lewis 的一篇经典文章

最初由 eygle 发布
[B]文章链接:
http://www.dbazine.com/jlewis22.shtml

有人说B*Tree索引最高能有24层，Lewis试图证明这个限制。
文章详细说明了作者的思路和尝试。

Lewis也说，可能这个问题不具有更多的应用意义，但是这个思考过程值得我们学习。
解决一个问题，思路是最重要的。

而在证明这样一个问题的过程中，所需要的基础知识异常广泛。
所以能完全读懂这样一篇文章，我们都会有所收获。

我自己学习Oracle的方法也是由点及面。
大家可以看看由 How High Can You Go? 这样一个点可以延伸出怎样的面。

最后作者给出了一个简单的解决方案，令人拍案叫绝。 [/B]



好文. 尝试了一下作者的CASE. 却发现REVERSE 索引的存储好像与常规索引很不一样. 同样是VARCHAR2(1469), 在根块却能够存下远远不止一个叶节点的指针.


[PHP]
----- begin tree dump
branch: 0x13400022 322961442 (0: nrow: 9, level: 1)
   leaf: 0x13400023 322961443 (-1: nrow: 1 rrow: 1)
   leaf: 0x13400024 322961444 (0: nrow: 1 rrow: 1)
   leaf: 0x13400025 322961445 (1: nrow: 1 rrow: 1)
   leaf: 0x13400026 322961446 (2: nrow: 1 rrow: 1)
   leaf: 0x13400027 322961447 (3: nrow: 1 rrow: 1)
   leaf: 0x13400028 322961448 (4: nrow: 1 rrow: 1)
   leaf: 0x13400029 322961449 (5: nrow: 1 rrow: 1)
   leaf: 0x1340002a 322961450 (6: nrow: 1 rrow: 1)
   leaf: 0x1340002b 322961451 (7: nrow: 1 rrow: 1)
----- end tree dump
[/PHP]

后来, 变成了这样
[PHP]
----- begin tree dump
branch: 0x13400022 322961442 (0: nrow: 13, level: 2)
   branch: 0x13400032 322961458 (-1: nrow: 2, level: 1)
      leaf: 0x13400023 322961443 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400062 322961506 (0: nrow: 0 rrow: 0)
   branch: 0x13400063 322961507 (0: nrow: 2, level: 1)
      leaf: 0x1340002c 322961452 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400030 322961456 (0: nrow: 0 rrow: 0)
   branch: 0x13400065 322961509 (1: nrow: 2, level: 1)
      leaf: 0x1340002d 322961453 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400064 322961508 (0: nrow: 0 rrow: 0)
   branch: 0x13400033 322961459 (2: nrow: 2, level: 1)
      leaf: 0x13400024 322961444 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400031 322961457 (0: nrow: 0 rrow: 0)
   branch: 0x13400067 322961511 (3: nrow: 2, level: 1)
      leaf: 0x1340002e 322961454 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400066 322961510 (0: nrow: 0 rrow: 0)
   branch: 0x13400035 322961461 (4: nrow: 2, level: 1)
      leaf: 0x13400025 322961445 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400034 322961460 (0: nrow: 0 rrow: 0)
   branch: 0x13400069 322961513 (5: nrow: 2, level: 1)
      leaf: 0x1340002f 322961455 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400068 322961512 (0: nrow: 0 rrow: 0)
   branch: 0x13400037 322961463 (6: nrow: 2, level: 1)
      leaf: 0x13400026 322961446 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400036 322961462 (0: nrow: 0 rrow: 0)
   branch: 0x13400039 322961465 (7: nrow: 2, level: 1)
      leaf: 0x13400027 322961447 (-1: nrow: 1 rrow: 1)
      leaf: 0x13400038 322961464 (0: nrow: 0 rrow: 0)
   branch: 0x1340003b 322961467 (8: nrow: 2, level: 1)
      leaf: 0x13400028 322961448 (-1: nrow: 1 rrow: 1)
      leaf: 0x1340003a 322961466 (0: nrow: 0 rrow: 0)
   branch: 0x1340003d 322961469 (9: nrow: 2, level: 1)
      leaf: 0x13400029 322961449 (-1: nrow: 1 rrow: 1)
      leaf: 0x1340003c 322961468 (0: nrow: 0 rrow: 0)
   branch: 0x1340003f 322961471 (10: nrow: 3, level: 1)
      leaf: 0x1340002a 322961450 (-1: nrow: 1 rrow: 1)
      leaf: 0x1340003e 322961470 (0: nrow: 0 rrow: 0)
      leaf: 0x1340002b 322961451 (1: nrow: 1 rrow: 1)
   branch: 0x13400061 322961505 (11: nrow: 1, level: 1)
      leaf: 0x13400040 322961472 (-1: nrow: 0 rrow: 0)
----- end tree dump
[/PHP]

使用道具 举报

回复
hooman
论坛徽章:
2
ITPUB元老 日期:2005-03-02 12:45:52授权会员 日期:2005-10-30 17:05:33
13#
发表于 2005-3-1 12:54 | 只看该作者

难道说REVERSE 索引和HASH 索引类似?

我觉得, REVERSE 索引更像是使用了一种特定HASH 函数(就是在BYTE 上进行翻转操作)的 HASH 索引.

不知道大家以为对吗?

使用道具 举报

回复
biti_rainy
论坛徽章:
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
14#
发表于 2005-3-1 13:59 | 只看该作者
REVERSE  就是一个函数索引

你要左插入的话，可以根据其特点，选择合适的数据。

使用道具 举报

回复
hooman
论坛徽章:
2
ITPUB元老 日期:2005-03-02 12:45:52授权会员 日期:2005-10-30 17:05:33
15#
发表于 2005-3-1 14:28 | 只看该作者
最初由 biti_rainy 发布
[B]REVERSE  就是一个函数索引

你要左插入的话，可以根据其特点，选择合适的数据。 [/B]


我的意思是, 如果用REVERSE 索引, 就很难做到让一个BLOCK 只能容纳一个索引指针了.  我原以为像lpad(1, 1469,'0') 这样的数据进行Reverse运算后仍然需要占用1469 BYTE 的空间, 但看起来不是这样.

使用道具 举报

回复
eagle_fan
论坛徽章:
27
授权会员 日期:2005-10-30 17:05:33管理团队成员 日期:2011-05-07 01:45:082012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:36优秀写手 日期:2013-12-18 09:29:13马上有车 日期:2014-02-19 11:55:14马上有房 日期:2014-02-19 11:55:14
16#
发表于 2005-3-3 12:03 | 只看该作者
最初由 hooman 发布
[B]

我的意思是, 如果用REVERSE 索引, 就很难做到让一个BLOCK 只能容纳一个索引指针了.  我原以为像lpad(1, 1469,'0') 这样的数据进行Reverse运算后仍然需要占用1469 BYTE 的空间, 但看起来不是这样. [/B]


我来解答楼上的疑问吧
我们只需要找到一个函数fun(x)做到
reverse(fun(x))=lpad(x,1469,'0')就可以了
而显然fun(x)为reverse(lpad(x,1469,'0'))

基于这个理论，看下面这个试验过程就清楚了
SQL> create table t2(
  2  v2 varchar2(1469));

Table created.

SQL> create index t2_i on t2(v2) reverse;

Index created.

SQL> begin
  2  for i in reverse 1..24 loop
  3  dbms_output.put_line(i);
  4  insert into t2 values (reverse(lpad(i,1469,'0')));
  5  end loop;
  6  end;
  7  /
SQL> select file_id,block_id ,segment_name from dba_extents
  2  where segment_name='T2_I';

   FILE_ID BLOCK_ID SEGMENT_NA
---------- -------- ----------
         1    82401 T2_I
         1    82465 T2_I
         1    82497 T2_I
         1    82529 T2_I
         1    82561 T2_I
         1    82593 T2_I
         1    82625 T2_I
         1    82657 T2_I
         1    82689 T2_I
         1    82721 T2_I

10 rows selected.

SQL> alter system dump datafile 1 block 82402;

System altered.

我们看dump下来的root node

*** 2005-03-03 11:32:30.000
Start dump data blocks tsn: 0 file#: 1 minblk 82402 maxblk 82402
buffer tsn: 0 rdba: 0x004141e2 (1/82402)
scn: 0x0000.0000de2a seq: 0x01 flg: 0x02 tail: 0xde2a0601
frmt: 0x02 chkval: 0x0000 type: 0x06=trans data
Block header dump:  0x004141e2
Object id on Block? Y
seg/obj: 0x18a7  csc: 0x00.de29  itc: 1  flg: -  typ: 2 - INDEX
     fsl: 0  fnx: 0x0 ver: 0x01

Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0x0001.003.0000013b  0x008098cc.0016.01  -BU-    1  fsc 0x0000.0000de2a

Branch block dump
=================
header address 50139204=0x2fd1044
kdxcolev 23
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x83: opcode=3: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 23
kdxconro 1
kdxcofbo 30=0x1e
kdxcofeo 440=0x1b8
kdxcoavs 410
kdxbrlmc 4277036=0x41432c
kdxbrsno 0
kdxbrbksz 1916

其中
kdxcolev 23可以看到确实达到了23level

使用道具 举报

回复
eagle_fan
论坛徽章:
27
授权会员 日期:2005-10-30 17:05:33管理团队成员 日期:2011-05-07 01:45:082012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:36优秀写手 日期:2013-12-18 09:29:13马上有车 日期:2014-02-19 11:55:14马上有房 日期:2014-02-19 11:55:14
17#
发表于 2005-3-3 13:21 | 只看该作者
最初由 hooman 发布
[B]

我的意思是, 如果用REVERSE 索引, 就很难做到让一个BLOCK 只能容纳一个索引指针了.  我原以为像lpad(1, 1469,'0') 这样的数据进行Reverse运算后仍然需要占用1469 BYTE 的空间, 但看起来不是这样. [/B]


上面只是在reverse index下达到了Jonathan Lewis的试验目的，再来试着解释一下hooman不能成功搭起24层的原因
重复hooman的试验

SQL> create table test2
  2  (v varchar2(1469));

Table created.

SQL> create index test2_i on test2(v) reverse;

Index created.

SQL> begin
  2   for i in reverse 1..24 loop
  3   dbms_output.put_line(i);
  4   insert into test2 values (lpad(i,1469,'0'));
  5   end loop;
  6   end;
  7  /

PL/SQL procedure successfully completed.

SQL> select file_id,block_id ,segment_name from dba_extents
  2  where segment_name='TEST2_I';

   FILE_ID   BLOCK_ID                                                           
---------- ----------                                                           
SEGMENT_NAME                                                                    
--------------------------------------------------------------------------------
         1      82465                                                           
TEST2_I      


SQL> select object_name,object_id from dba_objects
  2  where object_name='TEST2_I';

OBJECT_NAME                                                                     
--------------------------------------------------------------------------------
OBJECT_ID                                                                     
----------                                                                     
T3_I                                                                           
      6319     

SQL> alter session set events 'immediate trace name treedump level 6319';

Session altered.

SQL> analyze index test2_i validate structure;

Index analyzed.

   SQL> select lf_blks,lf_rows_len,br_blks,br_rows_len from index_stats;

   LF_BLKS LF_ROWS_LEN    BR_BLKS BR_ROWS_LEN
---------- ----------- ---------- -----------
        24       35568          1         221

首先我们发现叶子节点还是24个，所以还是一个block存放了一个index entry。但是branch node的数量大大减少了(就是根，一个），我们使用24层的例子达到的是如下
SQL> analyze index t1_i1 validate structure;

Index analyzed.

SQL> select lf_blks,lf_rows_len,br_blks,br_rows_len from index_stats;

   LF_BLKS LF_ROWS_LEN    BR_BLKS BR_ROWS_LEN                                   
---------- ----------- ---------- -----------                                   
        24       35568        276       33992   

所以怀疑是branch node中存放的方式发生了变化，导致可以存放多行
进一步看dump中的内容
首先看treedump的内容
----- begin tree dump
branch: 0x414222 4276770 (0: nrow: 24, level: 1)
   leaf: 0x414223 4276771 (-1: nrow: 1 rrow: 1)
Leaf block dump
===============
header address 1808443484=0x6bcaa85c
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 4
kdxconro 1
kdxcofbo 38=0x26
kdxcofeo 412=0x19c
kdxcoavs 374
kdxlespl 0
kdxlende 0
kdxlenxt 4276785=0x414231
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 1892
row#0[412] flag: -----, lock: 2
col 0; len 1469; (1469):
30 31 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
col 1; len 6; (6):  00 41 41 f0 00 00
----- end of leaf block dump -----
   leaf: 0x414231 4276785 (0: nrow: 1 rrow: 1)
Leaf block dump
。。。
发现果然每个叶子还是存放一条记录
dump branch node来看（这里就是root）
SQL> select dbms_utility.data_block_address_file(4276770)
  2  ,dbms_utility.data_block_address_block(4276770)
  3  from dual;

DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(4276770)
---------------------------------------------
DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(4276770)
----------------------------------------------
                                            1
                                         82466

Start dump data blocks tsn: 0 file#: 1 minblk 82466 maxblk 82466
buffer tsn: 0 rdba: 0x00414222 (1/82466)
scn: 0x0000.0000e2cd seq: 0x01 flg: 0x06 tail: 0xe2cd0601
frmt: 0x02 chkval: 0x9919 type: 0x06=trans data
Block header dump:  0x00414222
Object id on Block? Y
seg/obj: 0x18af  csc: 0x00.e2cc  itc: 1  flg: -  typ: 2 - INDEX
     fsl: 0  fnx: 0x0 ver: 0x01

Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0x0008.006.0000012e  0x008097ff.0016.03  --U-    1  fsc 0x0000.0000e2cd

Branch block dump
=================
header address 50139204=0x2fd1044
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x81: opcode=1: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 1
kdxconro 23
kdxcofbo 74=0x4a
kdxcofeo 1741=0x6cd
kdxcoavs 1667
kdxbrlmc 4276771=0x414223
kdxbrsno 2
kdxbrbksz 1916
row#0[1813] dba: 4276785=0x414231
col 0; len 2; (2):  30 32
col 1; TERM
row#1[1888] dba: 4276775=0x414227
col 0; len 1; (1):  31
col 1; TERM
row#2[1741] dba: 4276794=0x41423a
col 0; len 2; (2):  31 31
col 1; TERM
row#3[1821] dba: 4276784=0x414230
col 0; len 2; (2):  31 32
col 1; TERM
row#4[1895] dba: 4276774=0x414226
col 0; len 1; (1):  32
col 1; TERM
row#5[1749] dba: 4276793=0x414239
col 0; len 2; (2):  32 31
col 1; TERM
row#6[1829] dba: 4276783=0x41422f
col 0; len 2; (2):  32 32
col 1; TERM
row#7[1902] dba: 4276773=0x414225
col 0; len 1; (1):  33
col 1; TERM
row#8[1757] dba: 4276792=0x414238
col 0; len 2; (2):  33 31
col 1; TERM
row#9[1837] dba: 4276782=0x41422e
col 0; len 2; (2):  33 32
col 1; TERM
row#10[1909] dba: 4276772=0x414224
col 0; len 1; (1):  34
col 1; TERM
row#11[1765] dba: 4276791=0x414237
col 0; len 2; (2):  34 31
col 1; TERM
row#12[1845] dba: 4276781=0x41422d
col 0; len 2; (2):  34 32
col 1; TERM
row#13[1853] dba: 4276780=0x41422c
col 0; len 1; (1):  35
col 1; TERM
row#14[1773] dba: 4276790=0x414236
col 0; len 2; (2):  35 31
col 1; TERM
row#15[1860] dba: 4276779=0x41422b
col 0; len 1; (1):  36
col 1; TERM
row#16[1781] dba: 4276789=0x414235
col 0; len 2; (2):  36 31
col 1; TERM
row#17[1867] dba: 4276778=0x41422a
col 0; len 1; (1):  37
col 1; TERM
row#18[1789] dba: 4276788=0x414234
col 0; len 2; (2):  37 31
col 1; TERM
row#19[1874] dba: 4276777=0x414229
col 0; len 1; (1):  38
col 1; TERM
row#20[1797] dba: 4276787=0x414233
col 0; len 2; (2):  38 31
col 1; TERM
row#21[1881] dba: 4276776=0x414228
col 0; len 1; (1):  39
col 1; TERM
row#22[1805] dba: 4276786=0x414232
col 0; len 2; (2):  39 31
col 1; TERM
----- end of branch block dump -----
End dump data blocks tsn: 0 file#: 1 minblk 82466 maxblk 82466

发现0好像都省略掉了（0的ASC码为30）

所以想用append 1来试试看

使用道具 举报

回复
eagle_fan
论坛徽章:
27
授权会员 日期:2005-10-30 17:05:33管理团队成员 日期:2011-05-07 01:45:082012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:362012新春纪念徽章 日期:2012-02-13 15:11:36优秀写手 日期:2013-12-18 09:29:13马上有车 日期:2014-02-19 11:55:14马上有房 日期:2014-02-19 11:55:14
18#
发表于 2005-3-3 13:33 | 只看该作者
重复上面的试验，只是换用1来append

SQL> create table t3
  2  (v varchar2(1469));

Table created.

SQL> create index t3_i on t3(v) reverse;

Index created.

SQL> begin
  2   for i in reverse 1..24 loop
  3   dbms_output.put_line(i);
  4   insert into t3 values (lpad(i,1469,'1'));
  5   end loop;
  6   end;
  7  /

PL/SQL procedure successfully completed.

SQL> select object_name,object_id from dba_objects
  2  where object_name='T3_I';

OBJECT_NAME                                                                     
--------------------------------------------------------------------------------
OBJECT_ID                                                                     
----------                                                                     
T3_I                                                                           
      6317     

SQL> alter session set events 'immediate trace name treedump level 6317';

Session altered.

SQL> analyze index t3_i validate structure;

Index analyzed.

SQL> select lf_blks,lf_rows_len,br_blks,br_rows_len,height from index_stats;

   LF_BLKS LF_ROWS_LEN    BR_BLKS BR_ROWS_LEN     HEIGHT
---------- ----------- ---------- ----------- ----------
        24       35568         10       13469          3

发现叶子节点不变，还是24个，但是branch数增加了,为10个，并且height增加为3

先看treedump
----- begin tree dump
branch: 0x414362 4277090 (0: nrow: 9, level: 2)
   branch: 0x414374 4277108 (-1: nrow: 5, level: 1)
      leaf: 0x414363 4277091 (-1: nrow: 1 rrow: 1)
Leaf block dump
===============
header address 1808279644=0x6bc8285c
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 4
kdxconro 1
kdxcofbo 38=0x26
kdxcofeo 412=0x19c
kdxcoavs 374
kdxlespl 0
kdxlende 0
kdxlenxt 4277105=0x414371
kdxleprv 0=0x0
kdxledsz 0
kdxlebksz 1892
row#0[412] flag: -----, lock: 2
col 0; len 1469; (1469):
30 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
col 1; len 6; (6):  00 41 43 50 00 00
----- end of leaf block dump -----
。。。。。

1的ASC码值为31，一目了然

dump branch node下来看看

SQL> select dbms_utility.data_block_address_file(4277108),
  2       dbms_utility.data_block_address_block(4277108)
  3  from dual;

DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(4277108)                                   
---------------------------------------------                                   
DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(4277108)                                 
----------------------------------------------                                 
                                            1                                   
                                         82804                                 
                                                                                


SQL> alter system dump datafile 1 block 82804;

System altered.

Start dump data blocks tsn: 0 file#: 1 minblk 82804 maxblk 82804
buffer tsn: 0 rdba: 0x00414374 (1/82804)
scn: 0x0000.0000e20b seq: 0x01 flg: 0x02 tail: 0xe20b0601
frmt: 0x02 chkval: 0x0000 type: 0x06=trans data
Block header dump:  0x00414374
Object id on Block? Y
seg/obj: 0x18ad  csc: 0x00.e20a  itc: 1  flg: -  typ: 2 - INDEX
     fsl: 0  fnx: 0x0 ver: 0x01

Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0x0009.008.00000114  0x008094a7.0015.01  -BU-    1  fsc 0x0000.0000e20b

Branch block dump
=================
header address 68030532=0x40e1044
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x83: opcode=3: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 8
kdxconro 4
kdxcofbo 36=0x24
kdxcofeo 413=0x19d
kdxcoavs 377
kdxbrlmc 4277091=0x414363
kdxbrsno 0
kdxbrbksz 1916
row#0[413] dba: 4277105=0x414371
col 0; len 2; (2):  30 32
col 1; TERM
row#1[421] dba: 4277095=0x414367
col 0; len 1; (1):  31
col 1; TERM
row#2[428] dba: 4277122=0x414382
col 0; len 1469; (1469):
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
col 1; len 4; (4):  00 41 43 59
row#3[1908] dba: 4277104=0x414370
col 0; len 2; (2):  31 32
col 1; TERM
----- end of branch block dump -----
End dump data blocks tsn: 0 file#: 1 minblk 82804 maxblk 82804

我们可以看到他把很多11111存放在了一起（row 2)，从而达到了存放多个条目的目的

使用道具 举报

回复
hooman
论坛徽章:
2
ITPUB元老 日期:2005-03-02 12:45:52授权会员 日期:2005-10-30 17:05:33
19#
发表于 2005-3-4 11:58 | 只看该作者
eagle_fan, Thanks a lot!
这么一DUMP, 就基本明白了

使用道具 举报

回复
hooman
论坛徽章:
2
ITPUB元老 日期:2005-03-02 12:45:52授权会员 日期:2005-10-30 17:05:33
20#
发表于 2005-3-4 12:00 | 只看该作者
最初由 eagle_fan 发布
[B]

我来解答楼上的疑问吧
我们只需要找到一个函数fun(x)做到
reverse(fun(x))=lpad(x,1469,'0')就可以了
而显然fun(x)为reverse(lpad(x,1469,'0'))


PFPF

使用道具 举报

回复

123下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

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