This article will be discussing Reverse Binary Tree index feature of Oracle database, an index which is there to solve block contention problem. It will be discussing how it works, what are its advantages and its limitations. When a normal binary tree index based on a numeric column populated by a sequence, it gives rise to hot block problem. Applications trying to insert new rows will face “buffer busy wait”, because everyone wants to write to same block. This problem is called hot block or block contention.
How it works
Reverse Binary Tree index take index values and simply reverse them before inserting into block. For example index value 123456 will be reversed like 654321 and next value 123457 will be reversed like 754321 and will be inserted into some other block because there is very slight change in values of first two values (123456 and 123457) and a big change in second two values (654321 and 754321). Using this strategy, subsequent sequence values will not be inserted in same block and insert load will be distributed evenly across index leaf blocks.
Advantages
- Its major benefit is to resolve block contention issue. This issue can be important in an Oracle Real Application Clusters (Oracle RAC) database where multiple instances continuously update the same leaf block.
- Index data access will be faster as the numbers of branch nodes need to be referred are reduced
Limitations
Because values are not stored sequentially in blocks so optimizer will not use reverse binary tree index for range scan. i.e. 123456 is stored in different block then 123457. This can be verified by CLUSTERING_FACTOR column of USER_INDEXES view which indicates the amount of order of the rows in the table based on the values of the index.
Example
We will create a table, add some rows into it and then will create normal and reverse binary tree indexes on it one after the other and verify that values are distributed across leaf blocks instead of adding them in blocks sequentially.
SQL> CREATE TABLE atable (
2 anumber NUMBER,
3 avarchar VARCHAR2(50)
4 );
Table created.
SQL> BEGIN
2 FOR i IN 1..10000 LOOP
3 INSERT INTO atable VALUES (i, 'i');
4 END LOOP;
5 END;
6 /
PL/SQL procedure successfully completed.
SQL> COMMIT;
Commit complete.
SQL> CREATE INDEX anumber_indx ON atable(anumber);
Index created.
SQL> EXEC DBMS_STATS.GATHER_TABLE_STATS(USER, 'ATABLE');
PL/SQL procedure successfully completed.
SQL> SELECT i.index_name, t.blocks, t.num_rows, i.clustering_factor
2 FROM user_tables t, user_indexes i
3 WHERE t.table_name = i.table_name
4 AND i.index_name = 'ANUMBER_INDX';
INDEX_NAME BLOCKS NUM_ROWS CLUSTERING_FACTOR
------------------------------ ---------- ---------- -----------------
ANUMBER_INDX 20 10000 20Here CLUSTERING_FACTOR is exactly same as the number of blocks, it means table is very well ordered and index entries in a single leaf block tend to point to rows in the same data blocks. But it will have block contention problem. Now let’s check reverse binary tree index.
SQL> DROP INDEX anumber_indx;
Index dropped.
SQL> CREATE INDEX anumber_rev_indx ON atable(anumber) REVERSE;
Index created.
SQL> EXEC DBMS_STATS.GATHER_TABLE_STATS(USER, 'ATABLE');
PL/SQL procedure successfully completed.
SQL> SELECT i.index_name, t.blocks, t.num_rows, i.clustering_factor
2 FROM user_tables t, user_indexes i
3 WHERE t.table_name = i.table_name
4 AND i.index_name = 'ANUMBER_REV_INDX';
INDEX_NAME BLOCKS NUM_ROWS CLUSTERING_FACTOR
------------------------------ ---------- ---------- -----------------
ANUMBER_REV_INDX 20 10000 2124You can see that table is very randomly ordered. In this case, it is unlikely that index entries in the same leaf block point to rows in the same data blocks and it will avoid block contention problem.