Order of keys inside index blocks

In this post we are going to illustrate how index keys are ordered inside a leaf block of an Oracle B+tree index.

It is well known that index blocks share most of their structure with “regular” (heap) table blocks; in particular, they share most of the way entries are stored inside the block. In tables, a row can be placed anywhere in the bottom part of the block (which is essentially managed like an “heap”, in which the exact memory address that the row is stored at is not important); its row address is recorded into one of the slots of a vector named “row directory”, located near the beginning of the block.

The address of the row is not published externally: only its position inside the row directory is (as the last part of the rowid, usually named “row number”), in order to enable the kernel to move the row inside the “bottom heap” as it likes – all it has to do is to update the row directory with the new address after the move, and the change will be perfectly transparent to the outside world. This of course enables the optimal utilization of the limited space inside the block, since space inside it can be re-organized at will.

Index entries are stored in the index blocks in exactly the same fashion (and probably much of the code that manages them is the very same, since, for example, they are frequently named “rows” in block dumps and documentation, a convention we will keep in this post). The only difference is that the position inside the row directory is not published as well (there is not such thing as a “keyid” that needs to be known outside of the block); the kernel uses this additional degree of freedom to keep the row directory ordered by key value (in binary order).

Let’s check it by using this test case. The script creates a table and defines a one-column index on it:

create table t (x varchar2(10));

create index t_idx on t(x);

and then inserts eight rows in “random” order:

insert into t values('000000');

insert into t values('777777');

insert into t values('111111');

insert into t values('666666');

insert into t values('222222');

insert into t values('555555');

insert into t values('333333');

insert into t values('444444');

The block dump (in 11.1.0.7) of the leaf (and root) block reveals the following index keys (my annotations are enclosed in curly braces):

...

kdxlebksz 8036

row#0[8020] flag: ------, lock: 2, len=16

col 0; len 6; (6): 30 30 30 30 30 30 { '000000' }

col 1; len 6; (6): 01 00 1c 74 00 00

row#1[7988] flag: ------, lock: 2, len=16

col 0; len 6; (6): 31 31 31 31 31 31 { '111111' }

col 1; len 6; (6): 01 00 1c 74 00 02

row#2[7956] flag: ------, lock: 2, len=16

col 0; len 6; (6): 32 32 32 32 32 32 { '222222' }

col 1; len 6; (6): 01 00 1c 74 00 04

row#3[7924] flag: ------, lock: 2, len=16

col 0; len 6; (6): 33 33 33 33 33 33 { '333333' }

col 1; len 6; (6): 01 00 1c 74 00 06

row#4[7908] flag: ------, lock: 2, len=16

col 0; len 6; (6): 34 34 34 34 34 34 { '444444' }

col 1; len 6; (6): 01 00 1c 74 00 07

row#5[7940] flag: ------, lock: 2, len=16

col 0; len 6; (6): 35 35 35 35 35 35 { '555555' }

col 1; len 6; (6): 01 00 1c 74 00 05

row#6[7972] flag: ------, lock: 2, len=16

col 0; len 6; (6): 36 36 36 36 36 36 { '666666' }

col 1; len 6; (6): 01 00 1c 74 00 03

row#7[8004] flag: ------, lock: 2, len=16

col 0; len 6; (6): 37 37 37 37 37 37 { '777777' }

col 1; len 6; (6): 01 00 1c 74 00 01

----- end of leaf block dump -----

...

The address where the “row” (actually an index key) is stored is dumped between square brackets; for example, row#0 (which is the ‘000000′ entry) is stored at address [8020], near the end of the block. You might note that the rows are placed bottom-up in insert order (the first row that was inserted was ‘000000′ and was placed at [8020]; the second was ‘777777′ and was placed at [8004], right above the first, etcetera); they are not ordered by binary value.

The binary dump of the portion of the block containing the “row directory” is

C6E0280 00000000 00001F64 1F341F54 1EF41F14 [....d...T.4.....]

C6E0290 1F041EE4 1F441F24 10E81128 106810A8 [....$.D.(.....h.]

removing auxiliary tracing info, grouping the bytes in two-byte chunks and converting them in decimal, we have

1F64=8036 end of "bottom heap" (kdxlebksz), also 8020 + 16

1F34=7988 address of '111111'

1F54=8020 address of '000000'

1EF4=7924 address of '333333'

1F14=7956 address of '222222'

1F04=7940 address of '555555'

1EE4=7908 address of '444444'

1F44=8004 address of '777777'

1F24=7972 address of '666666'

Page 1 of 2 | Next page