Databases Reference
In-Depth Information
“Athens” for example). An index defined with a key that contains more than one col-
umn is known as a composite index.
Composite indexes can be used to efficiently search a database table, given a more
complex SQL search criterion. As an example, the query
SELECT empNo, empName, empAddress, jobTitle
FROM employee
WHERE jobTitle = 'database administrator'
AND city = 'Los Angeles'
AND totalPur < 500;
results in the access to a set of target rows in the employee table that is typically a small
subset of the entire population of rows, but usually significantly more than a single row.
Using search methods based on a single attribute key will not work here, and frequent
exhaustive scans of the entire base table are usually prohibitively expensive.
We can easily extend the B+tree indexing method to handle more complex queries
of this type, commonly implemented in all the major database management systems
(DBMSs). In Section 2.2, we used B+trees to implement the concept of a unique index
based on a primary key, and accessing a single row. Now we wish to use the same general
structure to implement a nonunique index capable of accessing a set of rows that satisfy
a query with WHERE and AND conditions. In a unique index, the nonleaf nodes con-
tain key-pointer pairs where the key is the primary key of the table you want to access.
In a nonunique index, the key field is a concatenation of all the attributes you want to
set up to access the set of rows desired. We form a nonunique index key by concatenat-
ing the secondary keys for job title, city, and total amount of purchases, as shown in the
example in Figure 2.3.
The leaf nodes for unique indexes contain the complete set of primary key values,
with each key value paired with a pointer to the block containing the row with the given
primary key value. For the nonunique leaf nodes, we also have key-pointer pairs, but the
key values are the complete set of all combinations of the composite key that actually
occur in existing rows. If a composite key value occurs in
k
rows, then there are
k
key-
pointer pairs required to point to those rows, with the given key value repeated
k
times.
The analysis of a B+tree composite index proceeds in the same way as for a simple
key index, with the new definition of key fields accounting for the composite of
attributes. We note that this method of accessing the
k
target rows once at the end of the
B+tree search of concatenated keys is much faster than searching for the target rows over
and over for each individual key using multiple simple indexes. It is certainly possible to
do this, but for
k
keys in the composite index, you would have to search the index
k
times, and for each time, retrieve far more pointers to target rows for that key than you
would for the
k
rows that have the specific values you are looking for in all keys. We
illustrate this efficiency in the example that follows.
