Oracle versions 7-8
Oracle's default form of index is the b*tree index segment. This is a sorted list of row identifiers that can be accessed by a balanced tree. This tip won't go into binary sort algorithms and index balancing, but as a quick reminder, the basic idea is that, if you're looking up the row with the indexed last name 'SMITH', you check to see if 'SMITH' is in the first half (A-M) or the last (N-Z), then in the N-Z block to see if 'SMITH' is in the first half of that (N-S) or the last (T-Z), then in the N-S block to see if it's in N-O-P or Q-R-S, and then you can rapidly match it under S for an index unique access. Two notable advantages of this kind of indexing are that it works with any sequence of values, as long as they're sorted, and that it is more efficient the longer the sequence.
The blocks in an Oracle index segment form a doubly-linked list as well as a tree-sorted list. This is to optimize index range scanning. If a query needs to retrieve rows for June through July from a large table, it can look up June and then scan blocks by means of the list pointers until it reaches August. This works because the indexed values are sorted.
A logical implication of this indexing scheme is that if an indexed row
is deleted, the free space left in the index segment cannot be
reclaimed immediately. The indexed rowids have to be in sorted order,
so there is no way that the next indexed item can be written into the
first free space. Oracle also needs to allow for rollbacks; it cannot
be sure, until a
This means that the indexes of volatile tables are in danger of bloating, as I like to call it. Index bloating occurs when more and more space in the index segment is unused because indexed rows are deleted but never replaced. In extreme cases the majority of the blocks in the index segment are empty. I have seen a case in which one index wasted 800 megabytes of disk. This imposes a high penalty on an index range scan; naturally, index unique access is less affected.
This situation can be fairly easily rectified by rebuilding indexes.
Oracle allows index rebuilding while users are connected and working.
This is the syntax:
An index of a static or slowly changing table is in no danger of bloating. So it is not a good idea to write a script that rebuilds all the indexes in a tablespace or a database. Most of the CPU cycles consumed by such a script are wasted.
Instead, indexes should be periodically checked for usage and only
those that use far more space than they need should be rebuilt. The
Oracle data dictionary includes a temporary table called
Some senior DBAs advocate rebuilding any index that uses less than 75 percent of its allocated space. This seems a reasonable rule of thumb.