7 Using Extensible Indexing

B-tree

No index structure can satisfy all needs, but the self-balancing B-tree index comes closest to optimizing the performance of searches on large sets of data. Each B-tree node holds multiple keys and pointers. The maximum number of keys in a node supported by a specific B-tree is the order of that tree. Each node has a potential of order+1 pointers to the level below it. For example, the order=2 B-tree illustrated in Figure 7-1 has tree pointers: to child nodes whose value is less than the first key, to the child nodes whose value is greater than the first key and less than the second key, and to the child nodes whose value is greater than the second key. Thus, the B-tree algorithm minimizes the number of reads and writes necessary to locate a record by passing through fewer nodes than in a binary tree algorithm, which has only one key and at most two children for each decision node. Here we describe the Knuth variation in which the index consists of two parts: a sequence set that provides fast sequential access to the data, and an index set that provides direct access to the sequence set.

Although the nodes of a B-tree generally do not contain the same number of data values, and they usually contain a certain amount of unused space, the B-tree algorithm ensures that the tree remains balanced and that the leaf nodes are at the same level.

Figure 7-1 B-tree Index Structure

Description of "Figure 7-1 B-tree Index Structure"

Hash

Hashing gives fast direct access to a specific stored record based on a given field value. Each record is placed at a location whose address is computed as some function of some field of that record. The same function is used to insert and retrieve.

The problem with hashing is that the physical ordering of records has little if any relation to their logical ordering. Also, there can be large unused areas on the disk.

Figure 7-2 Hash Index Structure

Description of "Figure 7-2 Hash Index Structure"

k-d tree

Data that has two dimensions, such as latitude and longitude, can be stored and retrieved efficiently using a variation on the k-d tree known as the 2-d tree.

In this structure, each node is a datatype with fields for information, the two co-ordinates, and a left-link and right-link, which can point to two children.

Figure 7-3 2-d Index Structure

Description of "Figure 7-3 2-d Index Structure"

This structure is good at range queries. That is, if the user specifies a point (xx, xx) and a distance, the query returns the set of all points within the specified distance of the original point.

2-d trees are easy to implement. However, because a 2-d tree containing k nodes can have a height of k, insertion and querying can be complex.

Point Quadtree

Figure 7-4 Point Quadtree Index Structure

Description of "Figure 7-4 Point Quadtree Index Structure"

The point quadtree is also used to represent point data in a two dimensional spaces, but these structures divide regions into four parts where 2-d trees divide regions into two. The fields of the record type for this node comprise an attribute for information, two co-ordinates, and four compass points (such as NW, SW, NE, SE) that can point to four children.

Like 2-d trees, point quadtrees are easy to implement. However, like 2-d trees, a point quadtree containing k nodes can have a height of k, so insertion and querying can be complex. Each comparison requires comparisons on at least two co-ordinates. In practice, though, the lengths from root to leaf tend to be shorter in point quadtrees.

Non-Index-Based Functional Implementations

To define the Text indextype, the indextype designer must:

1. Define and code the functional implementation for the supported operator

   The Text indextype supports an operator called Contains, which accepts a text value and a key, and returns a number indicating whether the text contains the key. The functional implementation of this operator is a regular function defined as:

   CREATE FUNCTION TextContains(Text IN VARCHAR2, Key IN VARCHAR2)
   RETURN NUMBER AS
   BEGIN
   .......
   END TextContains;
   
   

2. Create the new operator and bind it to the functional implementation

   CREATE OPERATOR Contains
    BINDING (VARCHAR2, VARCHAR2) RETURN NUMBER USING TextContains;
   
   

3. Define a type that implements the index interface ODCIIndex

   This involves implementing routines for index definition, index maintenance, and index scan operations. Oracle calls:

   • The index definition routines (ODCIIndexCreate, ODCIIndexAlter, ODCIIndexDrop, ODCIIndexTruncate) to perform the appropriate operations when the index is created, altered, or dropped, or the base table is truncated

   • The index maintenance routines (ODCIIndexInsert, ODCIIndexDelete, ODCIIndexUpdate) to maintain the text index when table rows are inserted, deleted, or updated

   • The index scan routines (ODCIIndexStart, ODCIIndexFetch, ODCIIndexClose) to scan the text index and retrieve rows of the base table that satisfy the operator predicate

   CREATE TYPE TextIndexMethods
   (
   STATIC FUNCTION ODCIIndexCreate(...)
   ...
   );
   CREATE TYPE BODY TextIndexMethods
   (
   ...
   );
   
   

4. Create the Text indextype schema object

   The indextype definition specifies the operators supported by the new indextype and the type that implements the index interface.

   CREATE INDEXTYPE TextIndexType
   FOR Contains(VARCHAR2, VARCHAR2)
   USING TextIndexMethods;
   
   

Index-Based Functional Implementations

If you are creating an index-based functional implementation, you perform the same operations as for non-index-based functional implementations, but in a different order:

1. Define the implementation type

2. Define and code the functional implementation

3. Create the operator

4. Create the indextype

This order is required because definition of an index-based functional implementation requires the implementation type as a parameter.