This discussion is archived
12 Replies Latest reply: Oct 15, 2012 5:31 AM by Turlock22 RSS

How B-tree indexes works?

967454 Newbie
Currently Being Moderated
How B-tree indexes work internally in Oracle engine? How they are useful in retreving queries result faster?

Suppose a table EMP has 2 columns: Emp_ID and Emp_Address

We have an index on column Emp_ID of this table. Now how could it gives the result faster if I want to select Employee with Emp_ID = 1234?

Can any one help by taking this example??
  • 1. Re: How B-tree indexes works?
    Marco V. Expert
    Currently Being Moderated
    Have a look at this link:
    http://mattfleming.com/node/192
  • 2. Re: How B-tree indexes works?
    Marco V. Expert
    Currently Being Moderated
    Have a look at this link too:
    http://docs.oracle.com/cd/E14072_01/server.112/e10713/indexiot.htm
  • 3. Re: How B-tree indexes works?
    rp0428 Guru
    Currently Being Moderated
    Welcome to the forum!

    Whenever you post provide your 4 digit Oracle version (result of SELECT * FROM V$VERSION)
    >
    How B-tree indexes work internally in Oracle engine? How they are useful in retreving queries result faster?

    Suppose a table EMP has 2 columns: Emp_ID and Emp_Address

    We have an index on column Emp_ID of this table. Now how could it gives the result faster if I want to select Employee with Emp_ID = 1234?

    Can any one help by taking this example??
    >
    For how they work technically the links in the other replies should help. For why they are useful just use your own experience.

    Have you ever used a telephone book to find the telephone number of a friend living in your city?

    Did you notice that at the top of each page is the first and last name of the page? And that the pages themselves are in alphabetical order? That is an index.

    If the phone book just listed everyone randomly you would have to do a 'full table scan' and read every entry to find your friend's phone number.

    But because the phone book is 'indexed' you can easily find the page that your friends number 'might be' on by looking at the 'first name - last name' at the top of the page.

    Once you find the correct page you can then easily scan the page (which is roughly equivalent to an index leaf block) and find your friends name.

    Another example is a bookstore. You can walk in and look in every section and every shelf to find the book you want (full library scan) or you can use the computer to look up the book (index) and it will tell you the section and information (ISBN, author, title) about the book and then you can go to that exact section.
  • 4. Re: How B-tree indexes works?
    967454 Newbie
    Currently Being Moderated
    Thanks

    MY Oracle Version:
    Oracle Database 11g Enterprise Edition Release 11.1.0.7.0 - 64bit Production

    I know this basics about indexes, but I want to know about B- Tress in Particular.

    I have heard that **B- TREES indexes are good for columns which have high cardinality, however BITMAP indexes are good for columns having low cardinality**

    Can anyone explain what is the reason behind this?
  • 5. Re: How B-tree indexes works?
    Marco V. Expert
    Currently Being Moderated
    Have a look at this link:
    http://www.oracle.com/technetwork/articles/sharma-indexes-093638.html
  • 6. Re: How B-tree indexes works?
    Aman.... Oracle ACE
    Currently Being Moderated
    How about searching the same in the Performance Tuning guide within documentation?
    http://docs.oracle.com/cd/E11882_01/server.112/e16638/data_acc.htm#i17778

    Aman....
  • 7. Re: How B-tree indexes works?
    Mark Malakanov (user11181920) Expert
    Currently Being Moderated
    Did you notice that at the top of each page is the first and last name of the page? And that the pages themselves are in alphabetical order? That is an index.
    In general it is similar, but it is not how B-Tree indexing works.

    I'd say: for example your friends name is Joe. Imagine a phone book is two volume book. Volume One is The Index. Book Two is The List.

    You open Book One on first page and it says:
    if a Name first letter is less than or equal M open Page 358 otherwise open Page 359.
    You open Page 358 and it says:
    if a Name first letter is less than or equal G open Page 146 otherwise open Page 147.
    You open Page 147 and it says:
    if a Name first letter is less than or equal J open Page 175 otherwise open Page 176.
    You open Page 175 and it says:
    if a Name first letter is less than or equal H open Page 187 otherwise open Page 188.
    You open Page 188 and it says:
    if a Name first letter is less than or equal I open Page 192 otherwise open Page 191.
    You open Page 191 and it says:
    if a Name second letter is less than or equal M open Page 200 otherwise open Page 201.

    (ok lets stop it here, imagine there is not that many names from JN* to JZ* - Joanna, Joe, John, Joseph... - all fit into one page)

    You open Page 201 and it says:
    Leaf page!
    And there is a list of names from JN* to JZ*.
    (in Oracle these names may be in any order). Here you have to read-scan through whole page to find a row with name JOE.
    In a row with JOE you will see:
    Open a Book Two, page 1769, row 177.

    You open it and you see Joe's phone number (and may be other info).
  • 8. Re: How B-tree indexes works?
    967454 Newbie
    Currently Being Moderated
    Apart from index basics, I want to know for B- Tree index logics and BITMAP..
  • 9. Re: How B-tree indexes works?
    Girish Sharma Guru
    Currently Being Moderated
    Prashant Verma wrote:
    Apart from index basics, I want to know for B- Tree index logics and BITMAP..
    Ok, then be a regular reader of http://richardfoote.wordpress.com/

    Apart from above regular reading, I hope below PDF may be of your first interest :

    Oracle B-Tree Index Internals By Richard Foote:
    http://www.dbafan.com/book/oracle_index_internals.pdf

    And :

    Expert Indexing in Oracle Database 11g By Darl Kuhn, Sam R. Alapati and Bill Padfield
    http://www.amazon.com/Expert-Indexing-Oracle-Database-11g/dp/143023735X

    Regards
    Girish Sharma
  • 10. Re: How B-tree indexes works?
    Turlock22 Newbie
    Currently Being Moderated
    Google how bitmap indexes work, once you understand how they work you'll see why they're so good for low cardinallity (and bad for high cardinallty).
    Also a point about bitmap indexes is that as they work in binary they are extremely efficient when it comes to CPU usage, they work very close to machine code.
  • 11. Re: How B-tree indexes works?
    311441 Employee ACE
    Currently Being Moderated
    965342 wrote:
    Google how bitmap indexes work, once you understand how they work you'll see why they're so good for low cardinallity (and bad for high cardinallty).
    Actually, if you google a little bit more thoroughly you'll see that's not quite true:

    http://richardfoote.wordpress.com/2010/04/13/so-what-is-a-good-cardinality-estimate-for-a-bitmap-index-column-song-2/

    Cheers

    Richard Foote
    http://richardfoote.wordpress.com
  • 12. Re: How B-tree indexes works?
    Turlock22 Newbie
    Currently Being Moderated
    Thanks Richard that was very interesting, opinion changed :o)

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points