Index clarification

kparthi · Apr 27, 2016 3:32AM

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

Paul Horth · Apr 27, 2016 3:41AM

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 · Apr 27, 2016 3:48AM

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.

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 .

Etbin · Apr 27, 2016 3:48AM

https://www.youtube.com/watch?v=coRJrcIYbF4

https://www.cs.usfca.edu/~galles/visualization/BTree.html

Regards

Etbin

Paul Horth · Apr 27, 2016 3:53AM

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 · Apr 27, 2016 3:55AM

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 · Apr 27, 2016 4:23AM

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 · Apr 27, 2016 5:16AM

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 · Apr 27, 2016 6:23AM

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 · Apr 27, 2016 6:24AM

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 · Apr 27, 2016 6:35AM

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

Forum Stats

Quick Links

Categories

Index clarification

Answers

Data

Databases

Development

Development Tools

Open Source

Programs

Forum Stats

Categories

Index clarification

Answers