- If your queries are going to look at only a certain amount of table data, indexes can improve the speed of your queries.
- Indexes are used in database to speeding query performance
- Indexes are logically and physically independent of the data in the associated table. Being independent structures, they require storage space.
- Index converts the "full table scan" into "index scan".
Btree Index
By default Oracle uses indexes called B*Tree indexes.
By default Oracle uses indexes called B*Tree indexes.
- Btree Index works by organizing a column value into tree structure.
- Armed with the column value and the ROWID, Oracle can quickly find the rows that have the value we are interested in.
- You can build the Btree index based on one or more columns in the table. Those column values are stored in the index.
Video Explanation
video link-1
video link-2
Another view -
How Btree Index works ?
B-tree indexes works by organizing a column value into a tree structure, which converts the full table scan into index scan.
Btree index does not store any NULL values.
Btree index does not store any NULL values.
Example
We have a table, EMP with two column EMP_ID and EMP_NAME. And 500 million rows in this table.
EMP_ID EMP_NAME
1 Rahim
3 karim
5 Jamal
2 Kamal
8 Mira
7 Nira
... ..........
Now create a Btree index on the EMP_ID column.
We have a table, EMP with two column EMP_ID and EMP_NAME. And 500 million rows in this table.
EMP_ID EMP_NAME
1 Rahim
3 karim
5 Jamal
2 Kamal
8 Mira
7 Nira
... ..........
Now create a Btree index on the EMP_ID column.
CREATE INDEX emp_id_index ON emp (emp_id) TABLESPACE INDX01;
Step-1: Index will be stored in database in a Btree structure.
Hence, armed with the column value and the ROWID, Oracle can quickly find the
rows that have the value we are interested in.Step-1: Index will be stored in database in a Btree structure.
- An index (emp_id_index) will be created in INDX01 Tablespace.
- Here all the EMP_ID will be stored in a btree structure in data block.
- Two types of block will be in the Btree - Brach block and leaf block.
- This index will have 500 million EMP_ID values.
- In the leaf block, all the EMP_ID will be sorted. And, with each EMP_ID will be associated with a ROWID. Rowid contains the address that tells Oracle exactly where that EMP_ID is located in the table.
Say we wanted to findout EMP_ID = 5. Part of our
index might look like this:
Column
Value ROWID
1 AAAL+ZAAEAAAAMOAGa
2 AAAL+ZAAEAAAAMOAGb
3 AAAL+ZAAEAAAAMOAGc
4 AAAL+ZAAEAAAAMOAGd
5 AAAL+ZAAEAAAAMOAGe
6 AAAL+ZAAEAAAAMOAGf
7 AAAL+ZAAEAAAAMOAG
In our case, Oracle will then very quickly find the index entry for 5 in the Btree, and read the associated ROWID. Based on the ROWID, it knows exactly where the row is in the table, and it will go read it.
Also, since the column values in the index are sorted, Oracle may not
need to perform a sort operation. For example a query like this:
SELECT empid, sal FROM
emp WHERE empid BETWEEN 3 AND 6 ORDER BY emp_id;
Will require a sort if there is no index, but since we
have an index on the EMP_ID column, in many cases oracle will not need to do a
sort as long as it uses that index to get the data we need.
How Indexes are stored in Database ?
When you create an index, Oracle automatically allocates an index segment to hold the index's data in a tablespace.
You can control allocation of space for an index's segment and use of this reserved space in the following ways:
Oracle can retrieve both index and table data in parallel.
Knowing the Structure of B-tree indexes
It is very important to know how this indexes actually work to use them to maximum benefit. The mechanism followed by balanced-tree indexes is as follows:
B-tree index has 3 parts:
1)Root
2)Branch blocks
3)Leaf blocks
Root is the centre-point from where all the branch blocks and leaf blocks is connected. A B-tree index has two types of blocks
1)Branch blocks
2)Leaf blocks
Branch blocks for Searching and Leaf blocks that Store values.
Branch blocks
Branch blocks store the minimum key prefix needed to make a branching decision between two keys. This technique enables the database to fit as much data as possible on each branch block.
The branch blocks contain a pointer to the child block containing the key.
The number of keys and pointers is limited by the block size.
If the blocks have n keys then they have n+1 pointers.
Leaf blocks
All leaf blocks are at the same depth from the root branch block.
The leaf blocks contain every indexed data value and a corresponding rowid used to locate the actual row. Each entry is sorted by (key, rowid). Within a leaf block, a key and rowid is linked to its left and right sibling entries.
As in case of lock, if the key is exact, the lock will open fast or else it will take time. And sorting with rowid is the fastest method to sort data in compare to rownum.
If the database scans the index for a value, then it will find this value in n I/Os where n is the height of the B-tree index (The height of the index is the number of blocks required to go from the root block to a leaf block).
This is the basic principle behind Oracle Database indexes.
How Indexes are stored in Database ?
When you create an index, Oracle automatically allocates an index segment to hold the index's data in a tablespace.
You can control allocation of space for an index's segment and use of this reserved space in the following ways:
- Set the storage parameters for the index segment to control the allocation of the index segment's extents.
- Set the PCTFREE parameter for the index segment to control the free space in the data blocks that constitute the index segment's extents.
Oracle can retrieve both index and table data in parallel.
Knowing the Structure of B-tree indexes
It is very important to know how this indexes actually work to use them to maximum benefit. The mechanism followed by balanced-tree indexes is as follows:
B-tree index has 3 parts:
1)Root
2)Branch blocks
3)Leaf blocks
1)Branch blocks
2)Leaf blocks
Branch blocks for Searching and Leaf blocks that Store values.
Branch blocks
Branch blocks store the minimum key prefix needed to make a branching decision between two keys. This technique enables the database to fit as much data as possible on each branch block.
The branch blocks contain a pointer to the child block containing the key.
The number of keys and pointers is limited by the block size.
If the blocks have n keys then they have n+1 pointers.
Leaf blocks
All leaf blocks are at the same depth from the root branch block.
The leaf blocks contain every indexed data value and a corresponding rowid used to locate the actual row. Each entry is sorted by (key, rowid). Within a leaf block, a key and rowid is linked to its left and right sibling entries.
As in case of lock, if the key is exact, the lock will open fast or else it will take time. And sorting with rowid is the fastest method to sort data in compare to rownum.
If the database scans the index for a value, then it will find this value in n I/Os where n is the height of the B-tree index (The height of the index is the number of blocks required to go from the root block to a leaf block).
This is the basic principle behind Oracle Database indexes.
What are the dvantages of B-tree Structure ?
- All leaf blocks of the tree are at the same depth, so retrieval of any record from anywhere in the index takes approximately the same amount of time.
- B-tree indexes automatically stay balanced.
- B-trees provide excellent retrieval performance for a wide range of queries, including exact match and range searches.
- Inserts, updates, and deletes are efficient, maintaining key order for fast retrieval.
- B-tree performance is good for both small and large tables and does not degrade as the size of a table grows.
- All blocks of the B-tree are three-quarters full on the average.
