CrazyEngineers
CrazyEngineers
  • Neeraj
    Neeraj

    Member • Jul 31, 2013

    Tutorial: Indexes In Oracle

    Let's try to understand what are indexes in oracle or any database. Consider a general scenario that we encounter in our daily life.. Suppose I have a book with me about C programming and Data structures which consists of 700 pages. I want to study about file concepts in C. Now, how can I find where I have the information in the book that I want? I need to go searching page by page and search for the concept that I require right? This consumes a lot of time. To avoid this time wastage, books come with an index that stores the page numbers against the name of each chapter,unti etc. This index helps us in saving hell lot of time because we can directly go to the page that we want.

    Same applies in databases too. An index is used to avoid wastage of time that is spent in searching for a particular record in a table.

    For example, consider the following table

    1

    If you run the following query on this table:

    select * from emp where empno=7844;

    it will go and scan each and every block of data starting from the top row till bottom row and when it finds empno 6844, it gives the result. This is a small table, consider the same operation on a table with 10 million rows, it will definitely consume a lot of time. This can be reduced by using index. An index can be created as follows:

    create index ind_1 on emp(empno);

    In the above statement, we are telling oracle to create an index named ind_1 on empno filed of table emp.
    When this index is created, one more table is formed in the back end that stores the address of each and every row. Following diagram will give a clean idea about it:

    2

    As shown in the diagram, every empno has a corresponding address which holds the address of each row of the emp table. Now whenever we want to extract row corresponding to a particular empno, we get the row very fastly compared to earlier method where we had no index.

    This is how indexes are helpful in databases..

    There are mainly four type of indexes which I will be discussing further in the comments.
    They are:

    --> B-Tree Index
    --> Reverse B-Tree Index
    --> Bitmap index
    --> Function based Index

    --Nick
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • Neeraj Sharma

    Member • Jul 31, 2013

    B-Tree Index


    In the previous doc I gave an overview of what an Index is? What is its purpose and how it is implemented generally. In this doc I will go into the type of Indexes in Oracle, the first of them is B-Tree Index.
    Consider my previous doc where I showed how a separate table containing the index column is formed along with the address of each row. Now if the index table also gets millions of rows, we still have to traverse that complete list right from starting. It will not be that time consuming but we can reduce this time too and that can be done using B-Tree Index. As all of you must be aware of a B-Tree, the index takes an approach of a B-Tree. Let's take an example: Suppose you have an index created on empno which ranges from 1 to 100. A B-Tree Index divides this as follows:
    3

    As shown in the diagram, in the tree, all the nodes less that the root node goes to left hand side and greater ones go to right hand side. At last, the remaining nodes are mapped as addresses. When we run the following query:

    select * from emp where empno=22;

    The index access is done as follows:
    -> First root node is checked which is 50. Now as 22 is less than 50, we go to left hand side and completely neglect the right hand part
    -> Now it is checked with node 25. As 22<25, we again go to left hand side.
    -> Now it is checked with 12, As 22>12, we go to right hand side, take the address and access the row.



    Quite clearly, we got the row in just 3 steps rather that scanning the whole index table if we go by older approach.
    Are you sure? This action cannot be undone.
    Cancel

  • Neeraj Sharma

    Member • Jul 31, 2013

    Reverse B-Tree Index

    Hello, in my previous post, I described about B-Tree Index, lets look as to what is a Reverse B-Tree index now. Consider a scenario where we have empno ranging from 1 to 200. Suppose I insert 3 more empno 201,202 and 203 in emp table, then the index table must update itself according to it. Now if I insert these 3 new records into the B-Tree index shown in previous post, we will see that they must go right-most. If I keep inserting more and more empno, they will keep going on to the rightmost box and as there will be many inserts going into the table at once, it will be resource intensive and will block the table.
    4
    Note: B-Tree indexing is implemented in back end as table itself but the search is done as explained in my previous post instead of the sequential search

    To prevent overloading of the boxes, we employ Reverse B-Tree. In this strategy, we reverse the keys that we have to insert. For example, if we have to insert 201,202 and 203 we reverse them as

    201 => 102
    202 => 202
    203 => 302

    and this reversed value is then inserted. This will cause the inserts to happen at different boxes rather than overloading the same box and the resource overhead is reduced as shown in the figure below..
    ​
    ​
    5
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register