B*Tree Reverse index

B*Tree Reverse index is one of the index types that is supported by oracle. It more or less behaves like b*tree unique & non-unique index but only difference is the way it constructs the tree. In this index, index value is stored in the reverse direction when compared to the values in the actual data table. This index is used in order to distribute the index data evenly across all the leaf index nodes if table data is skewed very high.

Like b*tree index, this index doesn’t understand NULL. This B*Tree Reverse index can be created on a single column or more than one column. More than one B*Tree Reverse index can be created for the same data table.

HOW TO VERIFY:

How to verify whether the created index is reverse index or not? Fire this query,

select index_type from user_indexes where index_name = 'DEPT_ID_INDX'

ð  This query would return “NORMAL/REV” (it means it is B*Tree index but of “Reverse” type)

LITTLE-KNOWN FACTS TO BE REMEMBERED:

·         If this B*Tree Reverse index is created on a column where the data is highly skewed, then the created index table will be much smaller than the index table created by other b*tree indexes on the same column. Reason is, when index table is created by this reverse index, it requires less number of BRANCH nodes to construct the binary tree. This is explained in the example.

ADVANTAGE:

·         It reduces the contention to access the leaf index nodes

·         Index data retrieval will be faster since number of BRANCH nodes need to be referred are reduced.

DISADVANTAGE:

·         The main disadvantage is the inability to perform index range scans as such values are now distributed all over the place, only fetch-by-key or full-index (table) scans can be performed.

·         Performance will be dreadful if this reverse index is created a column which is evenly distributed already because this reverse index might create very unbalanced tree.

EXAMPLE:

Create an employee table and inserts 11 records. The table will look like this,

DATA TABLE:

ROWID	empid	column2	column3	Deptid	column4	column5
AAAAA1	1	..	..	101	..	..
AAAAA2	2	..	..	102	..	..
AAAAA3	3	..	..	103	..	..
AAAAA4	4	..	..	104	..	..
AAAAA5	5	..	..	105	..	..
AAAAA6	6	..	..	106	..	..
AAAAA7	7	..	..	107	..	..
AAAAA8	8	..	..	108	..	..
AAAAA9	9	..	..	109	..	..
AAAAA10	10	..	..	171	..	..
AAAAA11	11	..	..	199	..	..

Fire this query against this table where the requirement is to display the all the attributes of an employee whose deptid id 103.

Select * from emp where deptid = 103;

To understand the importance and efficiency of this reverse index, first check the performance of b*tree non-unique index.

So, create normal b*tree non-unique index on this column, deptid (create index dept_id_index on emp(deptid)). Once this index is created, index table and binary tree will look like this,

B*TREE non-unique Index Table:

INDEX	ROWID
101	AAAAA1
102	AAAAA2
103	AAAAA3
104	AAAAA4
105	AAAAA5
106	AAAAA6
107	AAAAA7
108	AAAAA8
109	AAAAA9
171	AAAAA10
199	AAAAA11

B*TREE non-unique Index’s binary tree:

Root Node: 150 (root node)

Branch Node: 125,172,113,107,104,110,102,105,108,103,107,102 (nodes in rectangle)

Leaf Node:101,102, 103,104, 105,106, 107,108, 109,171, 199 (leaf nodes in yellow color)

Here, since data is not distributed evenly, binary tree is not balanced. It means left side of binary tree is more congested when compared to the right side. So, retrieving the leaf blocks (which are in leaf side) will take lot of time since lots of branch nodes need to be referred (because height of the tree is very high). Height is nothing but number of branch nodes between root node and leaf node.

Actual value to be referred	Access Path (or Height)	Height of each leaf node
101	150-125-113-107-104-102-101	7
102	150-125-113-107-104-102-103-102-102	9
103	150-125-113-107-104-102-103-102-103	9
104	150-125-113-107-104-102-103-104	8
105	150-125-113-107-104-105-105	7
106	150-125-113-107-104-105-106	7
107	150-125-113-107-110-108-107-107	8
108	150-125-113-107-110-108-107-108	8
109	150-125-113-107-110-108-109	7
171	150-175-171	3
199	150-175-199	3
Total Number of nodes to be referred if we have to refer all the index leaf nodes through the index		76

In the query, we refer 103, so it has to refer 1 root node+8 branch node before reaching the actual leaf node(103).

Performance will be improved if we reduce the number of BRANCH nodes need to be referred. This is actually achieved by using the reverse index.

Now, create the B*TREE Reverse index on the same column, deptid (create index dept_id_index on emp(deptid) REVERSE). The index table and binary tree will look this,

B*TREE Reverse Index Table:

INDEX	ROWID
101	AAAAA1
171	AAAAA10
201	AAAAA2
301	AAAAA3
401	AAAAA4
501	AAAAA5
601	AAAAA6
701	AAAAA7
801	AAAAA8
901	AAAAA9
991	AAAAA11

B*TREE Reverse Index’s binary tree:

Root Node: 150 (root node)

Branch Node: 250,750,125,375,625,875,180,560,935 (nodes in rectangle)

Leaf Node:101,171,201,301,401,501,601,701,801,901,991 (leaf nodes in yellow color)

Here, index value is reversed and forms the leaf nodes. since data is distributed evenly, now binary tree becomes balanced one. Now, height for all of the leaf nodes are even.

Actual value to be referred	Access Path (or Height)	Height of each leaf node
101	500-250-125-101	4
171	500-250-125-180-171	5
102	500-250-125-180-201	5
103	500-250-375-301	4
104	500-250-375-401	4
105	500-750-625-560-501	5
106	500-750-625-560-601	5
107	500-750-625-701	4
108	500-750-875-801	4
109	500-750-875-935-901	5
199	500-750-875-935-991	5
Total Number of nodes to be referred if we have to refer all the index leaf nodes through the index		50

In the query, we refer 103, so it only has to refer 1 root node+2 branch node before reaching the actual leaf node(301).