Index clarification

Paul Horth

Jonathan Lewis wrote:

Paul,

For Oracle, leaf blocks are connected through a doubly linked list so that you can walk the index in ascending or descending order without revisiting branch blocks, but within each leaf block the strategy is different, it's:

{directory}{heap}
Each index entry (consisting of (key,table rowid)) are added to the top of the heap (so the heap is unordered)
The directory is a list of pointers into the heap, and is updated so that walking the directory from 1st to last  will jump around the heap accessing the index entries in key order.
To maintain the directory the code may have to "push down" part of the directory to make space in the right place for the new entry.

Regards
Jonathan Lewis

Maybe I've misunderstood this from the docs:

"

Leaf Blocks

All leaf blocks are at the same depth from the root branch block. Leaf blocks store the following:

• The complete key value for every row
• ROWIDs of the table rows

All key and ROWID pairs are linked to their left and right siblings. They are sorted by (key, ROWID)."

Jonathan Lewis

Paul,

You haven't misunderstood the manual, the manual is wrong.

I've used the feedback form on the equivalent 12.1 manual page to explain the error.

Think about the costs - if you have a linked list connecting index entries then you'd have to walk through all the index entries in a leaf block to find the last index leaf block entry; similarly to insert an entry you'd have to walk the list to find out where to insert it - and you'd have to lock the block while you did it. Very resource-intensive, and low scalability.

Regards

Jonathan Lewis

Paul Horth

Jonathan Lewis wrote:

Paul,

You haven't misunderstood the manual, the manual is wrong.
I've used the feedback form on the equivalent 12.1 manual page to explain the error.

Think about the costs - if you have a linked list connecting index entries then you'd have to walk through all the index entries in a leaf block to find the last index leaf block entry; similarly to insert an entry you'd have to walk the list to find out where to insert it - and you'd have to lock the block while you did it. Very resource-intensive, and low scalability.

Regards
Jonathan Lewis

Trust me to believe the docs!

Jonathan Lewis

It's a mistake that everyone makes occasionally - just because they're right most of the time doesn't mean they're right all the time.

Regards

Jonathan Lewis

Unknown

See the diagram and text in the Oracle docs

https://docs.oracle.com/cd/E11882_01/server.112/e40540/indexiot.htm#CNCPT1170

Figure 3-1 illustrates the structure of a B-tree index. The example shows an index on the department_id column, which is a foreign key column in the employees table.
Figure 3-1 Internal Structure of a B-tree Index
 

Description of "Figure 3-1 Internal Structure of a B-tree Index

Branch Blocks and Leaf Blocks

A B-tree index has two types of blocks: branch blocks for searching and leaf blocks that store values. The upper-level branch blocks of a B-tree index contain index data that points to lower-level index blocks. In Figure 3-1, the root branch block has an entry 0-40, which points to the leftmost block in the next branch level. This branch block contains entries such as 0-10 and 11-19. Each of these entries points to a leaf block that contains key values that fall in the range.

A B-tree index is balanced because all leaf blocks automatically stay at the same depth. Thus, retrieval of any record from anywhere in the index takes approximately the same amount of time. The height of the index is the number of blocks required to go from the root block to a leaf block. The branch level is the height minus 1. In Figure 3-1, the index has a height of 3 and a branch level of 2.

Branch blocks store the minimum key prefix needed to make a branching decision between two keys. This technique enables the database to fit as much data as possible on each branch block. The branch blocks contain a pointer to the child block containing the key. The number of keys and pointers is limited by the block size.
The leaf blocks contain every indexed data value and a corresponding rowid used to locate the actual row. Each entry is sorted by (key, rowid). Within a leaf block, a key and rowid is linked to its left and right sibling entries. The leaf blocks themselves are also doubly linked. In Figure 3-1 the leftmost leaf block (0-10) is linked to the second leaf block (11-19).

Jonathan Lewis

The leaf blocks contain every indexed data value and a corresponding rowid used to locate the actual row. Each entry is sorted by (key, rowid). Within a leaf block, a key and rowid is linked to its left and right sibling entries. The leaf blocks themselves are also doubly linked. In Figure 3-1 the leftmost leaf block (0-10) is linked to the second leaf block (11-19).

And the highlighted sentence is the one that Paul Horth quoted. It's been been in the manuals since at least 9i, and it's wrong.

While the diagram and description is "hand-wavy" correct, several of the details are misleading (which is a kind way of saying "wrong but recognisable as an attempt at simplification").

Regards

Jonathan Lewis