Forum Stats

  • 3,815,638 Users
  • 2,259,064 Discussions
  • 7,893,194 Comments

Discussions

Index clarification

kparthi
kparthi Member Posts: 37
edited Apr 27, 2016 2:28PM in SQL & PL/SQL

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


Tagged:
kparthiPaul  HorthNimish GargJonathan Lewis888095
«1

Answers

  • Paul  Horth
    Paul Horth Member Posts: 3,402 Gold Trophy
    edited 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
  • kparthi
    kparthi Member Posts: 37
    edited 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.
    
    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
    Paul Horth Member Posts: 3,402 Gold Trophy
    edited Apr 27, 2016 4:04AM

    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

    kparthikparthi
  • Chris Hunt
    Chris Hunt Member Posts: 2,066 Gold Trophy
    edited 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.

    Paul  Horth
  • 888095
    888095 Member Posts: 18
    edited 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

    kparthi
  • SKP
    SKP Member Posts: 844 Gold Badge
    edited 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
    Jonathan Lewis Member Posts: 9,946 Blue Diamond
    edited 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

    888095
  • Jonathan Lewis
    Jonathan Lewis Member Posts: 9,946 Blue Diamond
    edited 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
    Jonathan Lewis Member Posts: 9,946 Blue Diamond
    edited 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

This discussion has been closed.