B*Tree, or what I call 'conventional', indexes are the most commonly used type of
indexing structure in the database. They are similar in implementation to a binary search
tree you might have learned about in a computer science course. Their goal is to minimize
the amount of time Oracle spends searching for data. Loosely speaking, the structure
might look like this, if you have an index on a number column:
+---------------+
| 50 and less--|--------+
+------|--more than 50 | |
| +---------------+ |
| |
| |
| |
+---------------+ +---------------+
+-----|-->= 100 | | >40 to 50 |
| | >90 to 100---|---+ | >30 to 40 |
| | >80 to 90 | | +---|-->20 to 30 |
| | >70 to 80 | | | | >10 to 20----|---+
| | >60 to 70 | | | | >0 to 10 | |
| | >50 to 60 | | | | less than 0 | |
| +---------------+ | | +---------------+ |
| | | |
| | | |
| | | |
| | | |
+---------------+ +---------------+ +---------------+ +---------------+
| 101, rowid | | 91, rowid | | 21, rowid | | 11, rowid |
| 102, rowid | | 92, rowid | | 22, rowid | | 12, rowid |
| 103, rowid |<->| 93, rowid |<->| 23, rowid |<->| 13, rowid |
| 104, rowid | | 94, rowid | | 24, rowid | | 14, rowid |
| .... | | .... | | .... | | .... |
+---------------+ +---------------+ +---------------+ +---------------+
The lowest level blocks in the tree, called LEAF NODES, contain every indexed key and a
rowid (rid in the picture) that points to the row it is indexing. The interior blocks,
above the leaf nodes, are known as branch blocks. They are used to navigate through the
structure. For example, if we wanted to find the value '42' in the index, we would start
at the top of the tree and go to the right. We would inspect that block and discover we
needed to go to the block in the range 'less than 50 to 40'. This block would be the leaf
block and would point us to the rows that contained the number 42. It is interesting to
note that the leaf nodes of the index are actually a doubly linked list. Once we find out
where to 'start' in the leaf nodes – once we have found that first 42 value – doing an
ordered scan (also known as an INDEX RANGE SCAN) of values is very easy. We don’t have to
navigate the structure any more, we just go forward through the leaf nodes. That makes
solving a predicate, such as the following, pretty simple:
where x between 20 and 30
Oracle finds the first index block that contains 20 and then just walks horizontally,
through the linked list of leaf nodes until it finally hits a value that is greater than
30.
---------------------------- end of quote ---------------------------------
Hopefully that is more clear. Each branch block has a whole bunch of ranges on it. We
navigate from branch to branch finding the right range. Each range points to the next
block (either yet another branch block or a leaf node).
It is not a simple LEFT/RIGHT -- its an N-Way tree with each branch block pointing to
many other blocks).
I haven't actually read the book from start to finish myself (well, I definitely did read
chapter 16 since I wrote that one and chapter 8 which Sean Dillon who works with me
wrote).
I read it piecemeal as a technical reviewer and only read the first drafts ;) It has be
well recieved so far though