B-Trees and Bitmapped Indexes

One new feature in both the Enterprise and Workgroup editions of Oracle7 Server for NT is the ability to use traditional key (B-tree)-based indexes and bitmapped indexes. Here's a quick look at both types of indexing.

Relational database management systems (RDBMSs) include catalogs or system tables that store definitions of database components such as tables, columns, and indexes. Subject tables consist of rows about entities such as employees or products. Link tables store information that lets an RDBMS join separate pieces of information (such as a supplier's name, how much product is in inventory, and sales) about a real-world item.

Well-designed relational database tables have a primary key field and an index based on that key; you can usually define as many other indexes as you want. For example, you can index a product table both on the product ID (the primary key) and the manufacturer ID (the foreign key). In this example, the foreign key is relating--or linking--data about a specific product to its manufacturer. An index is basically a lookup table containing actual key values (the product IDs, for example) and pointers to the complete record.

All RDBMSs support both sequential and indexed access to records. Sequential access reads data sequentially until it finds the row or rows you want. This brute-force approach works well for small tables in which all rows are physically clustered or in applications that must perform an action on every row.

Most RDBMSs use B-trees or some variation of them as the primary indexing method. B-trees store index data in a hierarchy (or tree) of pages. Each index page typically contains many index entries and pointers to the next page of entries. The advantage of B-tree indexes over sequential access is that, instead of scanning pages that contain raw data, the RDBMS has to look at only a few index pages until it finds pointers to the requested rows.

By reducing the number of read operations to data, bitmapped indexes offer better response time than traditional indexing methods such as B-tree indexes. The idea behind a bitmapped index is that one bit associates a specific value for an attribute with a row. For example, each distinct value in a column can have a bitmapped index consisting of 5 million bits­one for each record in the database. When a bit is on (1), the value occurs in the record; when the bit is off (0), the value doesn't occur. The index can identify records through their bitmap position, so bitmaps don't need pointers.

Bitmapped indexes offer several advantages, such as reduced storage overhead and the capability to do compression operations on indexes. Bitmapped indexes are best for data with few unique values (not, for example, a product ID column in which each record has a unique value). Bitmapped indexes are also best for nonvolatile data, so these indexes are often an important feature of data warehouses. Finally, bitmapped indexes are extremely useful if you use Oracle7 for decision support or for fine-tuning performance. However, because modifying bitmapped indexes can impose a tremendous amount of overhead, they aren't a good choice for OLTP (i.e., volatile-data) systems.

Hide comments


  • Allowed HTML tags: <em> <strong> <blockquote> <br> <p>

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.