ANBOB™

b-tree indexes are an important access path structure in database and file systems
key property: each possible search path has the same length.

b-tree structure has the following:

1,all leaf blocks of the tree are at the same depth
2,b-tree indexes automatically stay balanced.
3,all blocks of the b-tree are three-quarters full on the average.
4,b-trees provide excellent retrieval performance ofr a wide range of queries ,including exact match and range searches
5,all DML operation are effcient,maintaining key order for fast retrieval.

Initially, each index tree has one level. If the data in the table is very small, there may be only one index block. In that case, the leaf block and branch block are the same, as the data grows, the level increases and then there is a branch block and leaf block with a parent-child relationship(关系). The separator(分离) keys are just index keys that determine(决定) which values are stored in each block.

anbob@sql>create table testIDX (id number(10),name varchar2(20));

Table created.

anbob@sql>begin
  2  for i in 1..100 loop
  3  insert into testIDX values(i,'anbob'||mod(i,10));
  4  end loop;
  5  commit;
  6  end;
  7  /

PL/SQL procedure successfully completed.

anbob@sql>exec dbms_stats.gather_table_stats(user,'TESTIDX');

PL/SQL procedure successfully completed.

anbob@sql>create index idx_testidx_id on testidx(id);

Index created.
anbob@sql>select object_id from user_objects where object_name='IDX_TESTIDX_ID';

 OBJECT_ID
----------
     76997
Note:

Note:
Dump tree structure
Alter session set events ‘immediate trace name treedump leval <object-id> ‘;

anbob@sql>alter session set events 'immediate trace name treedump level 76997';

Session altered.

anbob@sql>select value from v$diag_info where name='Default Trace File'; 

VALUE
----------------------------------------------------------------------------------------------------
/ora11g/app/oracle/diag/rdbms/anbob/anbob/trace/anbob_ora_17145.trc

anbob@sql>ho vi /ora11g/app/oracle/diag/rdbms/anbob/anbob/trace/anbob_ora_17145.trc

----- begin tree dump
leaf: 0x1000213 16777747 (0: nrow: 100 rrow: 100)
----- end tree dump

anbob@sql>begin
 2  for i in 101..1000 loop
 3  insert into testIDX values(i,'anbob'||mod(i,10));
 4  end loop;
 5  commit;
 6  end;
 7  /

PL/SQL procedure successfully completed.

In trace ,look at that is split branch and leaf block
----- begin tree dump
branch: 0x1000213 16777747 (0: nrow: 2, level: 1)
 leaf: 0x1000214 16777748 (-1: nrow: 540 rrow: 540)
 leaf: 0x1000215 16777749 (0: nrow: 460 rrow: 460)
----- end tree dump

anbob@sql>select dbms_utility.DATA_BLOCK_ADDRESS_FILE('16777747'),dbms_utility.data_block_address_block('16777747') from dual;

DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE('16777747') DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK('16777747')
------------------------------------------------ -------------------------------------------------
 4                                               531

Index Branch block dump
anbob@sql>alter system dump datafile 4 block 531;

System altered.

Block header dump:  0x01000213
 Object id on Block? Y
 seg/obj: 0x12cc5  csc: 0x00.165cc3  itc: 1  flg: E  typ: 2 - INDEX
 brn: 0  bdba: 0x1000210 ver: 0x01 opc: 0
 inc: 0  exflg: 0

 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0x0007.006.00000390  0x00c000ea.0142.01  -BU-    1  fsc 0x0000.00165e2a
Branch block dump
=================
header address 10801740=0xa4d24c
kdxcolev 1    /* block level; 0 is leaf block;>0 is branch block */
KDXCOLEV Flags = - - -
kdxcolok 1
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y  /* v8 block */
kdxconco 2  /* Kdxconco : columns in key ;0 block not in b-tree */
kdxcosdc 1  /* Kdxcosdc :increment each time block is split or deleted */
kdxconro 1  -- Kdxconro:rows in the row index
kdxcofbo 30=0x1e  -- Kdxcofbo: free space beginning offset
kdxcofeo 8047=0x1f6f    --   Kdxcofeo: free space ending offset,first used byte
kdxcoavs 8017     -- Kdxcoavs available space in the block(committed),does not include space for committed split holes.
kdxbrlmc 16777748=0x1000214   --pointer to left—most child block
kdxbrsno 0  --slot modified by last service transaction; only defined for insert and delete row.-1 means kdxbrlmc
kdxbrbksz 8056
kdxbr2urrc 0
row#0[8047] dba: 16777749=0x1000215            --dba
col 0; len 3; (3):  c2 06 2a                       --separator key
col 1; TERM
----- end of branch block dump -----

Note: Each index block (branch or leaf) has a common structure and some additional information,depending on if it is a leaf or a branch block. The common structure called kdxco(Kernel  inDeX CommOn ) is defind is kdx3.h and has the following components.

kdxcolev ,The maximum number of levels in a b-tree is 24(0-23),a 24-level index with 2 rows per index block can hold 2*(3**23)~18.8 billion leaf rows.

The block ITL lock is used by a service transaction to signal that it is currently operation on a block, and no other transaction should attempt(尝试) to update the block. The field can only be cleared after the service transaction completes(by cleanout or rollback).the field is nonzero if and only if the service transaction ITL is held; that is , the   transaction need s to be cleaned out.
Each index block has a cache layer and a transaction layer containing the ITL information kdxbr is structure specific to branch blocks ,if a branch block is on any free list,its kdxconco is 0.

Index leaf block 
Each index leaf block contain the size of the rowed data in the row header in the field called kdxledsz


anbob@sql>alter system dump datafile 4 block 532;

System altered.

Trace file content:  
Block header dump:  0x01000214
 Object id on Block? Y
 seg/obj: 0x12cc5  csc: 0x00.165eb0  itc: 2  flg: E  typ: 2 - INDEX
 brn: 0  bdba: 0x1000210 ver: 0x01 opc: 0
 inc: 0  exflg: 0

 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0x0007.006.00000390  0x00c000ec.0142.01  CB--    0  scn 0x0000.00165e2a
0x02   0x0002.002.0000041a  0x00c0009e.011b.26  C---    0  scn 0x0000.00165e2c
Leaf block dump
===============
header address 10801764=0xa4d264
kdxcolev 0  --index leaf block
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 1
kdxconro 540
kdxcofbo 1116=0x45c
kdxcofeo 1116=0x45c
kdxcoavs 0
kdxlespl 0
kdxlende 0                   ----row marked deleted
kdxlenxt 16777749=0x1000215  ----next leaf block
kdxleprv 0=0x0               ----previous leaf block 
kdxledsz 0                      ----bytes in rowid data
kdxlebksz 8032               
row#0[1116] flag: ------, lock: 0, len=12
col 0; len 2; (2):  c1 02           -----val 1
col 1; len 6; (6):  01 00 02 0f 00 00  -----rowid
row#1[1128] flag: ------, lock: 0, len=12
col 0; len 2; (2):  c1 03                -- val 2
col 1; len 6; (6):  01 00 02 0f 00 01    --rowid
 …
anbob@sql>select dump(id,16) id, dump(rowid,16) r from testidx where id =1;

ID                   R
-------------------- -------------------------------------
Typ=2 Len=2: c1,2    Typ=69 Len=10: 0,1,2c,c4,1,0,2,f,0,0  

Note:
Non-unique index 
 Store the rowid like another column of the index key
 Each column has length and data pairs
 Kdxledsz is zero
When the number of rows is 0,the first entry in the row index is valid and points to the last row deleted from block.
This allows an empty leaf block to be located in the search tree.
 
Unique index
Kdxledsize is 6 and therefore this is a unique index using the restricted rowed that takes size bytes. It is  either a local partitioned index or a non-partition index. If it is a global partitioned index, the rowed would take ten bytes

打赏

微信扫一扫，打赏作者吧～