B-Tree and Indexes Oracle Tips by Burleson Consulting

During any discussion of indexes with Oracle, the subject of B-tree structure is always bandied about as if everyone knew exactly what is being talked about. However, unless you come from a computer science or academic programming background, all you may understand is that a B-tree is a special structure format for an index that allows rapid access of the data in the index. But exactly what is a B-tree? Let’s take a quick look at a B-tree structure in Figure 6.1before we go on. Each upper node is known as a branch, while the lowest levels are known as leaf nodes. Branches point to other branches or leaf nodes. Leaf nodes store value-rowid pairs.

Figure 6.1 Example of a B-tree.

The actual distribution will depend on the number of data values in each range of values in a B-tree, with the overall goal to reduce the number of required levels that must be traversed to get to a specific value. The advantages of a B-tree structure are:

* All leaf blocks are of the same depth (number of values).

* In the case of randomly entered data, the B-tree stays balanced automatically.

* All blocks of a B-tree index are three-quarters full (on the average), allowing insertion without rebuild.

* B-trees provide excellent performance for all types of selects.

* Insert, update, and deletes tend to be efficient in a B-tree structure.

* B-tree performance stays optimal even when tables vary from small to large.

Indexes and Their Usage

With concatenated indexes, Oracle8i and Oracle9i can use key compression on the leading index values that show repeating behavior. Key compression reduces the size required for the storage of concatenated indexes. In order to use key compression, the index must be concatenated to show a grouping piece and a unique piece. The grouping piece repeats, while the unique piece will generally vary within a unique group range value. Key compression cannot be used on a primary key or unique index with a single column used as the index value.

Indexes store column values in either B-tree or bitmap format. The B-tree format is used for high-cardinality data (data with many unique values, such as last name, date of birth, part number, etc.). The binary index is used for low-cardinality data (sex, true/false, race, etc.). Indexes improve the performance of queries sometimes one-hundredfold. Indexes are especially useful for:

* Searching for rows with specified index column values.

* Accessing tables in index column order

When you initially insert a great number of rows into a new table, such as with import or SQLLOADER, it is generally faster to create the table, insert the rows, and then create the index. If you create the index before inserting the rows, Oracle must update the index for every row inserted. However, if you are inserting using a PL/SQL routine from a flat database table into a more normal structure, indexes can speed the process considerably.

TIP: If you are using a sequence or a call to SYSDATE to populate a column that corresponds to a unique or primary key field, use a reverse key index to prevent “hot spotting” and unbalanced B-trees.

Oracle recommends that you do not explicitly define UNIQUE indexes on tables; uniqueness is strictly a logical concept and should be associated with the definition of a table. Therefore, define UNIQUE integrity constraints on the desired columns. Oracle enforces UNIQUE integrity constraints by automatically defining a unique index on the unique key. Exceptions to this recommendation are usually performance-related. For example, using a CREATE TABLE . . . AS SELECT with a UNIQUE constraint is very much slower than creating the table without the constraint and then manually creating the UNIQUE constraint via an ALTER TABLE command.

If indexes contain NULLs, the NULLs are considered distinct values. There is, however, one exception: If all the non-NULL values in two or more rows of an index are identical, the rows are considered identical; therefore, UNIQUE indexes prevent this from occurring. This does not apply if there are no non-NULL values—in other words, if the rows are entirely NULL.

Use of Normal Unique and Nonunique Indexes

For most situations, a normal index (i.e., not a bitmapped or reverse key) will be used. This type of index can be monolithic (all in one index, albeit with multiple extents) or partitioned and subpartitioned (divided automatically by Oracle into several different identically structured indexes with different data ranges). Another item to note is that, prior to Oracle8i, while you could specify the DESC keyword for compatibility reasons, it was ignored in practice. This does not happen in versions of Oracle later than Oracle8i, and the index will be built in descending order. The DESC keyword is not applicable to bitmapped indexes. Like function-based indexes, DESC type indexes are not used until they and their base table are analyzed.

A normal index can be unique, which enforces uniqueness on the column it is based on (primary key and unique indexes are of this type), or nonunique. If the primary key constraint, unique constraint, or UNIQUE command option is not specified either during CREATE or ALTER tables or CREATE INDEX, then the index is nonunique.

If an index is being used for high cardinality (few related table rows for a single value) or to enforce uniqueness (primary key or unique index), then for most cases it should be a normal index. However, improvements in performance for high cardinality, low update, or insert indexes have been reported by converting them to bitmapped indexes. Normal indexes should also be used when enforcing a normal relational-type primary-foreign key relationship. One caveat here is that if the column for a unique or primary key index is populated by a call to a sequence or to SYSDATE, then a reverse key index may be advantageous to prevent hot spotting caused by an unbalanced B-tree structure. Bitmapped indexes cannot be UNIQUE indexes.

Normal indexes are subject to index browning, a condition where deletes from the underlying tables cause leaf nodes to not be filled, resulting in long search times as Oracle “climbs” the tree to find good values. Generally, this can be determined by analyzing the indexes for a table and examining the Remote DBA_INDEXES or INDEX_ STATS views. The Remote DBA_INDEXES view has one row for each index in the database; the INDEX_STATS view has one row for the most recently analyzed index. I suggest the use of a code fragment like the one shown in Source 6.1 to populate a temporary table so that all of a table’s indexes can be examined at one time for problems.

SOURCE 6.1 Code fragment to analyze all the table indexes of an owner.

ACCEPT owner PROMPT 'Enter table owner name: '
ACCEPT table PROMPT 'Enter table name: '
SET HEADING OFF feedback OFF VERIFY OFF ECHO OFF RECSEP OFF PAGES 0
DEFINE cr = 'chr(10)'
SPOOL index_sz.sql
SELECT 'CREATE TABLE stat_temp AS SELECT * FROM index_stats WHERE orwnum<1;'||&&cr
FROM dual;
SELECT
'ANALYZE INDEX '||owner||'.'||index_name||' VALIDATE STRUCTURE;'||&&cr||
'INSERT INTO stat_temp SELECT * FROM index_stats;'||&&cr||
'COMMIT;'
FROM Remote DBA_indexes
WHERE owner=upper('&owner')
AND table_name=upper('&table');
SPOOL OFF
@index_sz.sql

Once a table’s indexes have been analyzed, you can query the stat_temp table to find the ratio between del_lf_rows_len and the sum of lf_rows_len and del_lf_rows_len. If this ratio exceeds 0.3 (i.e., 15 to 30 percent of the leaf rows are probably empty), then more than likely you have a browning problem. The report in Source 6.2 can be run to determine this and other data that will help determine index state.

SOURCE 6.2 Browning report for indexes.

rem  *****************************************************************
rem
rem  NAME: brown.sql
rem
rem  HISTORY:
rem  Date             Who              What
rem  --------  -------------------  ----------------------------------
rem   06/05/97  Mike Ault              Updated for Oracle 7.x
rem   09/27/99  Mike Ault           Verified for 8.x
rem   09/22/99  Mike Ault           Verified for 9.x
rem  FUNCTION:  Will show index browning for all indexes for a
rem              user.
rem  INPUTS:  owner = Table owner name.
rem  *********************************************************************
column value noprint new_value blocksize
define cr=chr(10)
select value from v$parameter where name='db_block_size';
accept tab_owner prompt 'Enter Table Owner for Indexes:'
set heading off verify off termout off pages 0 recsep 0 feedback off
spool index_sz.sql
select
      'create table stat_temp as select * from index_stats;'||&&cr||
      'truncate table stat_temp;' 
from dual;
select     
      'analyze index '||owner||'.'||index_name||
      ' validate structure;'||&&cr||
      'insert into stat_temp select * from index_stats;'||&&cr||
      'commit;'
from Remote DBA_indexes
where
      owner=upper('&&tab_owner');
spool off
set feedback on termout on lines 80
start index_sz.sql
insert into temp_size_table select name,trunc(used_space/&&blocksize)
from stat_temp;
rem drop table stat_temp;
clear columns
column del_lf_rows_len format 999,999,999 heading 'Deleted Bytes'
column lf_rows_len format 999,999,999 heading 'Filled Bytes'
column browning format 999.90 heading 'Percent|Browned'
start ttitle "Index Browning Report"
spool rep_out/browning.lst
select
      name,del_lf_rows_len,lf_rows_len,
      (del_lf_rows_len/decode((lf_rows_len+del_lf_rows_len),0,1,
       lf_rows_len+del_lf_rows_len))*100 browning
from
      stat_temp
where
      del_lf_rows_len>0;
spool off

See Code Depot for Full Scripts

---

This is an excerpt from Mike Ault, bestselling author of "Oracle 10g Grid and Real Application Clusters". You can buy it direct from the publisher for 30%-off and get instant access to the code depot of Oracle tuning scripts.

Expert Remote DBA BC is America's oldest and largest Remote DBA Oracle support provider.  Get real Remote DBA experts, call BC Remote DBA today.