Discussions
Categories
- 196.7K All Categories
- 2.2K Data
- 234 Big Data Appliance
- 1.9K Data Science
- 449.7K Databases
- 221.5K General Database Discussions
- 3.8K Java and JavaScript in the Database
- 31 Multilingual Engine
- 549 MySQL Community Space
- 477 NoSQL Database
- 7.9K Oracle Database Express Edition (XE)
- 3K ORDS, SODA & JSON in the Database
- 532 SQLcl
- 4K SQL Developer Data Modeler
- 186.8K SQL & PL/SQL
- 21.2K SQL Developer
- 295.3K Development
- 17 Developer Projects
- 138 Programming Languages
- 292K Development Tools
- 104 DevOps
- 3.1K QA/Testing
- 645.9K Java
- 27 Java Learning Subscription
- 37K Database Connectivity
- 153 Java Community Process
- 105 Java 25
- 22.1K Java APIs
- 138.1K Java Development Tools
- 165.3K Java EE (Java Enterprise Edition)
- 17 Java Essentials
- 157 Java 8 Questions
- 85.9K Java Programming
- 79 Java Puzzle Ball
- 65.1K New To Java
- 1.7K Training / Learning / Certification
- 13.8K Java HotSpot Virtual Machine
- 94.2K Java SE
- 13.8K Java Security
- 203 Java User Groups
- 24 JavaScript - Nashorn
- Programs
- 386 LiveLabs
- 37 Workshops
- 10.2K Software
- 6.7K Berkeley DB Family
- 3.5K JHeadstart
- 5.6K Other Languages
- 2.3K Chinese
- 170 Deutsche Oracle Community
- 1K Español
- 1.9K Japanese
- 230 Portuguese
Index clarification

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
Answers
-
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.
-
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 .
-
-
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
-
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.
-
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
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 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
-
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
-
I like the youtube video - demonstrating very clearly why B-trees are always balanced (i.e. same height top to bottom).
Regards
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