Skip to Main Content

SQL & PL/SQL

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

Index clarification

kparthiApr 27 2016 — edited Apr 27 2016

Hi All ,

I am having clarification on how index are stored .

I keep on reading that B-tree unique index are stored in sorted order( default ascending )

Indexes can be unique or nonunique. Unique indexes guarantee that no two rows of a table have duplicate values in the key column or columns. For example, no two employees can have the same employee ID. Thus, in a unique index, one rowid exists for each data value. The data in the leaf blocks is sorted only by key.


Question:

User "A" insert into a table with 1,3,5( My understanding is B-tree index is created with Root Block--->Branch Block-->Leaf Block for storing 1,3,5 in aceding order )

User "B" insert into a table with 2,3,6

(

-- Now the questin is how the index are stored in asceding order

  --is there any operation happening inisde the b-tree index so that the Leaf block is rebuilded

  -- or is there any different way the leaf block is created

)



create table test_index (a number primary key );

desc desc test_index;

desc test_index

Name Null     Type 

---- -------- ------

A    NOT NULL NUMBER

INDEX_NAME                     UNIQUENESS

------------------------------ ----------

SYS_C00413788                  UNIQUE

-- User A tries to insert 1 ,3 , 5

insert into test_index values (1);

insert into test_index values (3);

insert into test_index values (5);

commit;

-- My understanding is B-tree index is created with Root Block--->Branch Block-->Leaf Block for storing 1,3,5 in aceding order

-- User B tries to insert 2 ,4 , 6

insert into test_index values (2);

insert into test_index values (4);

insert into test_index values (6);

commit;

-- Now the questin is how the index are stored in asceding order

  --is there any operation happening inisde the b-tree index so that the Leaf block is rebuilded

  -- or is there any different way the leaf block is created

Comments

Paul Horth

No rebuilding necessary - the key/rowid pairs are stored as a doubly linked list.

A new row is placed in that list so it occupies the correct position.

kparthi

Paul Horth wrote:

No rebuilding necessary - the key/rowid pairs are stored as a doubly linked list.

A new row is placed in that list so it occupies the correct position.

AATRNiAADAAAAk3AAA1
AATRNiAADAAAAk3AAD2
AATRNiAADAAAAk3AAB3
AATRNiAADAAAAk3AAE4
AATRNiAADAAAAk3AAC5
AATRNiAADAAAAk3AAF6

My understanding from your input is that even with key/rowid pair it would have been stored in above method only . But its not in sorted order ..

If any example with explanation would be great for my level of understanding as i am having very little knowledge in indexes .

Paul Horth

Sorry, don't see your point. What has that list of rowids got to do with it?

The rowids aren't sorted, the keys are - by their position in a doubly linked list.

For example, your first insert of 1,3,5 gives

1 <-> 3 <-> 5

in the leaf block (the <-> indicating the double linked list pointers between the keys.

On adding, 2 you get

        --------------

        |            |

        v            v

1      3 <-> 5       2

^                    ^

|                    |

----------------------

With the pointers altered to reflect the ordering 1,2,3,5

Chris Hunt

Why do you care?

I've been working as an Oracle developer for over twenty years, and I don't know anything much about how Oracle stores its indexes. It's not important to me.

What is important is to know how Oracle use indexes to improve performance, types of index to use, the columns one should and shouldn't index, etc. All of that stuff is vitally important to understand, the internals of how it works I leave to Oracle themselves.

888095

Now the questin is how the index are stored in asceding order

> Please take a look at the algorithm about how btree works.


is there any operation happening inisde the b-tree index so that the Leaf block is rebuilded

> the link provided by Etbin demonstrates how it works

A good article you can go through to get your answer

http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals

Also do a search you will find so many links ( including the one which I liked most  https://richardfoote.wordpress.com/oracle-index-internals-seminar/).

Regards,

Biju Das

SKP

kparthi wrote:

AATRNiAADAAAAk3AAA 1
AATRNiAADAAAAk3AAD 2
AATRNiAADAAAAk3AAB 3
AATRNiAADAAAAk3AAE 4
AATRNiAADAAAAk3AAC 5
AATRNiAADAAAAk3AAF 6

My understanding from your input is that even with key/rowid pair it would have been stored in above method only . But its not in sorted order ..

If any example with explanation would be great for my level of understanding as i am having very little knowledge in indexes .

The rowid what you are showing are the rowid of the table . Those rowid store the data randomly in table and not the way linklist work .

But the address of the index will be something you can imagine what paul had said.

In your first 3 row :

ind address       table_data     table rowid

100                   1                  AATRNiAADAAAAk3AAA

101                   3                  AATRNiAADAAAAk3AAB

102                   5                  AATRNiAADAAAAk3AAC


after the next 3 row insert


ind address       table_data     table rowid

100                   1                  AATRNiAADAAAAk3AAA

101                   2                  AATRNiAADAAAAk3AAD

102                   3                  AATRNiAADAAAAk3AAB  -- 101 become 102 in index address give a place for data 2

103                   4                  AATRNiAADAAAAk3AAE

104                   5                  AATRNiAADAAAAk3AAC  -- 102 become 104 in index address give a place for data 4

105                   6                  AATRNiAADAAAAk3AAF


Jonathan Lewis

One confusing detail on the ToadWorld article is the use of "prev" to describe the "leftmost child" entry in a branch block:

kdxbrlmc 16779590=0x1000946<--Address to Prev Node

The leaf blocks have prv and nxt entries which refer to the previous and next leaf blocks in key order (and these are necessarily on the same level), while the "leftmost child" is talking about the next level down; referring to it as "Prev" carries a suggestion that it's pointing to a branch block on the same level.

Regards

Jonathan Lewis

Jonathan Lewis

I like the youtube video - demonstrating very clearly why B-trees are always balanced (i.e. same height top to bottom).

Regards

Jonathan Lewis

Jonathan Lewis

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

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-7404

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 follows

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

1 - 16
Locked Post
New comments cannot be posted to this locked post.

Post Details

Locked on May 25 2016
Added on Apr 27 2016
16 comments
685 views