Database System Concepts, 7th Ed.
©Silberschatz, Korth and Sudarshan
See www.db-book.com for conditions on re-use
Chapter 9: Indexing
©Silberschatz, Korth and Sudarshan9.2Database System Concepts - 7th Edition
Outline
▪ Basic Concepts
▪ Ordered Indices
▪ B+-Tree Index Files
▪ B-Tree Index Files
▪ Hashing
▪ Spatio-Temporal Indexing
©Silberschatz, Korth and Sudarshan9.3Database System Concepts - 7th Edition
Basic Concepts
▪ Indexing mechanisms used to speed up access to desired data.
• E.g., author catalog in a library
▪ Search Key – an attribute or a set of attributes used to look up records
in a file.
▪ An index file consists of records (called index entries) of the form
▪ Index files are typically much smaller than the original file
▪ Two basic kinds of indices:
• Ordered indices: search keys are stored in sorted order
• Hash indices: search keys are distributed uniformly across
“buckets” using a “hash function”.
search-key pointer
©Silberschatz, Korth and Sudarshan9.4Database System Concepts - 7th Edition
Index Evaluation Metrics
▪ Access types supported efficiently. e.g.,
• Records with a specified value in the attribute
• Records with an attribute value falling in a specified range of values.
▪ Access time
▪ Insertion time
▪ Deletion time
▪ Space overhead
©Silberschatz, Korth and Sudarshan9.5Database System Concepts - 7th Edition
Ordered Indices
▪ In an ordered index, index entries are stored on the search key value.
▪ Clustering index: in a sequentially ordered file, the index whose search
key specifies the sequential order of the file.
• Also called primary index
• The search key of a primary index is usually but not necessarily the
primary key.
▪ Secondary index: an index whose search key specifies an order
different from the sequential order of the file. Also called
nonclustering index.
▪ Index-sequential file: sequential file ordered on a search key, with a
clustering index on the search key.
©Silberschatz, Korth and Sudarshan9.6Database System Concepts - 7th Edition
Dense Index Files
▪ Dense index — Index record appears for every search-key value in the
file.
▪ E.g. index on ID attribute of instructor relation
©Silberschatz, Korth and Sudarshan9.7Database System Concepts - 7th Edition
Dense Index Files (Cont.)
▪ Dense index on dept_name, with instructor file sorted on dept_name
©Silberschatz, Korth and Sudarshan9.8Database System Concepts - 7th Edition
Sparse Index Files
▪ Sparse Index: contains index records for only some search-key
values.
• Applicable when records are sequentially ordered on search-key
▪ To locate a record with search-key value K we:
• Find the index record with the largest search-key value < K
• Search file sequentially starting at the record to which the index
record points
©Silberschatz, Korth and Sudarshan9.9Database System Concepts - 7th Edition
Sparse Index Files (Cont.)
▪ Compared to dense indices:
• Less space and less maintenance overhead for insertions and deletions.
• Generally slower than the dense index for locating records.
▪ Good tradeoff:
• For clustered index: sparse index with an index entry for every block in the
file, corresponding to the least search-key value in the block.
• For unclustered index: sparse index on top of dense index (multilevel index)
©Silberschatz, Korth and Sudarshan9.10Database System Concepts - 7th Edition
Secondary Indices Example
▪ Secondary index on salary field of instructor
▪ Index record points to a bucket that contains pointers to all the actual
records with that particular search-key value.
▪ Secondary indices have to be dense
©Silberschatz, Korth and Sudarshan9.12Database System Concepts - 7th Edition
Multilevel Index
▪ If the index does not fit in memory, access becomes expensive.
▪ Solution: treat the index kept on disk as a sequential file and construct a
sparse index on it.
• outer index – a sparse index of the basic index
• inner index – the basic index file
▪ If even the outer index is too large to fit in the main memory, yet another
level of the index can be created, and so on.
▪ Indices at all levels must be updated on insertion or deletion from the file.
©Silberschatz, Korth and Sudarshan9.13Database System Concepts - 7th Edition
Multilevel Index (Cont.)
©Silberschatz, Korth and Sudarshan9.16Database System Concepts - 7th Edition
Indices on Multiple Keys
▪ Composite search key
• E.g., index on instructor relation on attributes (name, ID)
• Values are sorted lexicographically
▪ E.g. (John, 12121) < (John, 13514) and
(John, 13514) < (Peter, 11223)
• Can query on just name, or on (name, ID)
©Silberschatz, Korth and Sudarshan9.18Database System Concepts - 7th Edition
Example of B+-Tree
©Silberschatz, Korth and Sudarshan9.19Database System Concepts - 7th Edition
B+-Tree Index Files (Cont.)
▪ All paths from the root to a leaf are of the same length
▪ Each node that is not a root or a leaf has between n/2 and n
children.
▪ A leaf node has between (n–1)/2 and n–1 values
▪ Special cases:
• If the root is not a leaf, it has at least 2 children.
• If the root is a leaf (that is, there are no other nodes in the tree), it
can have between 0 and (n–1) values.
A B+-tree is a rooted tree satisfying the following properties:
©Silberschatz, Korth and Sudarshan9.20Database System Concepts - 7th Edition
B+-Tree Node Structure
▪ Typical node
• Ki are the search-key values
• Pi are pointers to children (for non-leaf nodes) or pointers to records or
buckets of records (for leaf nodes).
▪ The search keys in a node are ordered
K1 < K2 < K3 < . . . < Kn–1
(Initially assume no duplicate keys, address duplicates later)
©Silberschatz, Korth and Sudarshan9.21Database System Concepts - 7th Edition
Leaf Nodes in B+-Trees
▪ For i = 1, 2, . . ., n–1, pointer Pi points to a file record with search-key value
Ki,
▪ If Li, Lj are leaf nodes and i < j, Li’s search-key values are less than or equal
to Lj’s search-key values
▪ Pn points to next leaf node in search-key order
Properties of a leaf node:
©Silberschatz, Korth and Sudarshan9.22Database System Concepts - 7th Edition
Non-Leaf Nodes in B+-Trees
▪ Non-leaf nodes form a multi-level sparse index on the leaf nodes. For a
non-leaf node with n pointers:
• All the search keys in the subtree to which P1 points are less than K1
• For 2  i  n – 1, all the search keys in the subtree to which Pi points
have values greater than or equal to Ki–1 and less than Ki
• All the search keys in the subtree to which Pn points have values
greater than or equal to Kn–1
• General structure
©Silberschatz, Korth and Sudarshan9.23Database System Concepts - 7th Edition
Example of B+-tree
▪ B+-tree for instructor file (n = 6)
▪ Leaf nodes must have between 3 and 5 values
((n–1)/2 and n –1, with n = 6).
▪ Non-leaf nodes other than root must have between 3 and 6
children ((n/2 and n with n =6).
▪ Root must have at least 2 children.
©Silberschatz, Korth and Sudarshan9.24Database System Concepts - 7th Edition
Observations about B+-trees
▪ Since the inter-node connections are done by pointers, “logically” close
blocks need not be “physically” close.
▪ The non-leaf levels of the B+-tree form a hierarchy of sparse indices.
▪ The B+-tree contains a relatively small number of levels
▪ Level below root has at least 2* n/2 values
▪ Next level has at least 2* n/2 * n/2 values
▪ .. etc.
• If there are K search-key values in the file, the tree height is no more
than  logn/2(K)
• thus searches can be conducted efficiently.
▪ Insertions and deletions to the main file can be handled efficiently, as the
index can be restructured in logarithmic time.
©Silberschatz, Korth and Sudarshan9.25Database System Concepts - 7th Edition
Queries on B+-Trees
function find(v)
1. C=root
2. while (C is not a leaf node)
1. Let i be least number s.t. V  Ki.
2. if there is no such number i then
3. Set C = last non-null pointer in C
4. else if (v = C.Ki ) Set C = Pi +1
5. else set C = C.Pi
3. if for some i, Ki = V then return C.Pi
4. else return null /* no record with search-key value v exists. */
©Silberschatz, Korth and Sudarshan9.26Database System Concepts - 7th Edition
Queries on B+-Trees (Cont.)
▪ Range queries find all records with search key values in a given range
• See book for details of function findRange(lb, ub) which returns set
of all such records
• Real implementations usually provide an iterator interface to fetch
matching records one at a time, using a next() function
©Silberschatz, Korth and Sudarshan9.27Database System Concepts - 7th Edition
Queries on B+-Trees (Cont.)
▪ If there are K search-key values in the file, the height of the tree is no
more than logn/2(K).
▪ A node is generally the same size as a disk block, typically 4 kilobytes
• and n is typically around 100 (40 bytes per index entry).
▪ With 1 million search key values and n = 100
• at most log50(1,000,000) = 4 nodes are accessed in a lookup
traversal from root to leaf.
▪ Contrast this with a balanced binary tree with 1 million search key values
— around 20 nodes are accessed in a lookup
• above difference is significant since every node access may need a
disk I/O, costing around 20 milliseconds
©Silberschatz, Korth and Sudarshan9.28Database System Concepts - 7th Edition
Non-Unique Keys
▪ If a search key ai is not unique, create instead an index on a composite
key (ai , Ap), which is unique
• Ap could be a primary key, record ID, or any other attribute that
guarantees uniqueness
▪ Search for ai = v can be implemented by a range search on a composite
key, with range (v, - ∞) to (v, + ∞)
▪ But more I/O operations are needed to fetch the actual records
• If the index is clustering, all accesses are sequential+
• If the index is non-clustering, each record access may need an I/O
operation
©Silberschatz, Korth and Sudarshan9.29Database System Concepts - 7th Edition
Updates on B+-Trees: Insertion
Assume a record is already added to the file. Let
l pr be a pointer to the record and let
l v be the search key value of the record
1. Find the leaf node in which the search-key value would appear
1. If there is room in the leaf node, insert (v, pr) pair in the leaf node
2. Otherwise, split the node (along with the new (v, pr) entry) as
discussed in the next slide, and propagate updates to parent nodes.
©Silberschatz, Korth and Sudarshan9.30Database System Concepts - 7th Edition
Updates on B+-Trees: Insertion (Cont.)
▪ Splitting a leaf node:
• take the n (search-key value, pointer) pairs (including the one being
inserted) in sorted order. Place the first n/2 in the original node, and
the rest in a new node.
• let the new node be p, and let k be the least key value in p. Insert
(k,p) in the parent of the node being split.
• If the parent is full, split it and propagate the split further up.
▪ Splitting of nodes proceeds upwards till a node that is not full is found.
• In the worst case, the root node may be split, increasing the tree's
height by 1.
Result of splitting node containing Brandt, Califieri and Crick on inserting Adams
Next step: insert entry with (Califieri, pointer-to-new-node) into parent
©Silberschatz, Korth and Sudarshan9.31Database System Concepts - 7th Edition
B+-Tree Insertion
B+-Tree before and after insertion of “Adams”
Affected nodes
©Silberschatz, Korth and Sudarshan9.32Database System Concepts - 7th Edition
B+-Tree Insertion
B+-Tree before and after insertion of “Lamport”
Affected nodes
Affected nodes
©Silberschatz, Korth and Sudarshan9.33Database System Concepts - 7th Edition
▪ Splitting a non-leaf node: when inserting (k,p) into an already full internal
node N
• Copy N to an in-memory area M with space for n+1 pointers and n
keys
• Insert (k,p) into M
• Copy P1,K1, …, K n/2-1,P n/2 from M back into node N
• Copy Pn/2+1,K n/2+1,…,Kn,Pn+1 from M into newly allocated node N'
• Insert (K n/2,N') into parent N
▪ Example
▪ Read pseudocode in book!
Insertion in B+-Trees (Cont.)
©Silberschatz, Korth and Sudarshan9.34Database System Concepts - 7th Edition
Examples of B+-Tree Deletion
▪ Deleting “Srinivasan” causes merging of under-full leaves
Before and after deleting “Srinivasan”
Affected nodes
©Silberschatz, Korth and Sudarshan9.35Database System Concepts - 7th Edition
Examples of B+-Tree Deletion (Cont.)
▪ Leaf containing Singh and Wu became underfull and borrowed a value
Kim from its left sibling
▪ Search-key value in the parent changes as a result
Before and after deleting “Singh” and “Wu”
Affected nodes
©Silberschatz, Korth and Sudarshan9.36Database System Concepts - 7th Edition
Example of B+-tree Deletion (Cont.)
▪ Node with Gold and Katz became underfull and was merged with its sibling
▪ Parent node becomes underfull and is merged with its sibling
• Value separating two nodes (at the parent) is pulled down when merging
▪ Root node then has only one child, and is deleted
Before and after deletion of “Gold”
©Silberschatz, Korth and Sudarshan9.37Database System Concepts - 7th Edition
Updates on B+-Trees: Deletion
Assume a record is already deleted from the file. Let V be the search key
value of the record, and Pr be the pointer to the record.
▪ Remove (Pr, V) from the leaf node
▪ If the node has too few entries due to the removal, and the entries in the
node and a sibling fit into a single node, then merge siblings:
• Insert all the search-key values in the two nodes into a single node
(the one on the left), and delete the other node.
• Delete the pair (Ki–1, Pi), where Pi is the pointer to the deleted node,
from its parent, recursively using the above procedure.
©Silberschatz, Korth and Sudarshan9.38Database System Concepts - 7th Edition
Updates on B+-Trees: Deletion
▪ Otherwise, if the node has too few entries due to the removal, but the
entries in the node and a sibling do not fit into a single node, then
redistribute pointers:
• Redistribute the pointers between the node and a sibling such that
both have more than the minimum number of entries.
• Update the corresponding search-key value in the parent of the node.
▪ The node deletions may cascade upwards till a node that has n/2 or
more pointers is found.
▪ If the root node has only one pointer after deletion, it is deleted and the
sole child becomes the root.
©Silberschatz, Korth and Sudarshan9.39Database System Concepts - 7th Edition
Complexity of Updates
▪ Cost (in terms of the number of I/O operations) of insertion and deletion of
a single entry proportional to the height of the tree
• With K entries and maximum fanout of n, worst case complexity of
insert/delete of an entry is O(logn/2(K))
▪ In practice, number of I/O operations is less:
• Internal nodes tend to be in a buffer
• Splits/merges are rare, most insert/delete operations only affect a leaf
node
▪ Average node occupancy depends on the insertion order
• 2/3rds with random, much more with insertion in sorted order
©Silberschatz, Korth and Sudarshan9.40Database System Concepts - 7th Edition
B+-Tree File Organization
▪ B+-Tree File Organization:
• Leaf nodes in a B+-tree file organization store records, instead of
pointers
• Helps keep data records clustered even when there are
insertions/deletions/updates
▪ Leaf nodes are still required to be half full
• Since records are larger than pointers, the maximum number of
records that can be stored in a leaf node is less than the number of
pointers in a non-leaf node.
▪ Insertion and deletion are handled in the same way as insertion and
deletion of entries in a B+-tree index.
©Silberschatz, Korth and Sudarshan9.41Database System Concepts - 7th Edition
B+-Tree File Organization (Cont.)
▪ Example of B+-tree File Organization
▪ Good space utilization is important since records use more space than
pointers.
▪ To improve space utilization, involve more sibling nodes in redistribution
during splits and merges
• Involving 2 siblings in redistribution (to avoid split/merge where
possible) results in each node having at least entries 3/2n
©Silberschatz, Korth and Sudarshan9.42Database System Concepts - 7th Edition
Bulk Loading and Bottom-Up Build
▪ Inserting entries one-at-a-time into a B+-tree requires  1 IO per entry
• assuming leaf level does not fit in memory
• can be very inefficient for loading a large number of entries at a time
(bulk loading)
▪ Efficient alternative 1:
• sort entries first (using efficient external-memory sort algorithms to be
discussed later)
• insert in sorted order
▪ insertion will go to an existing page (or cause a split)
▪ much improved IO performance, but most leaf nodes half full
▪ Efficient alternative 2: Bottom-up B+-tree construction
• As before sort entries
• And then create tree layer-by-layer, starting with leaf level
▪ details as an exercise
• Implemented as part of bulk-load utility by most database systems
©Silberschatz, Korth and Sudarshan9.45Database System Concepts - 7th Edition
B-Tree Index File Example
B-tree (above) and B+-tree (below) on same data
©Silberschatz, Korth and Sudarshan9.46Database System Concepts - 7th Edition
Hashing
©Silberschatz, Korth and Sudarshan9.47Database System Concepts - 7th Edition
Static Hashing
▪ A bucket is a unit of storage containing one or more entries (a bucket
is typically a disk block).
• we obtain the bucket of an entry from its search-key value using a
hash function
▪ Hash function h is a function from the set of all search-key values K to
the set of all bucket addresses B.
▪ Hash function is used to locate entries for access, insertion as well as
deletion.
▪ Entries with different search-key values may be mapped to the same
bucket; thus entire bucket has to be searched sequentially to locate an
entry.
▪ In a hash index, buckets store entries with pointers to records
▪ In a hash file organization buckets store records
©Silberschatz, Korth and Sudarshan9.48Database System Concepts - 7th Edition
Handling of Bucket Overflows
▪ Bucket overflow can occur because of
• Insufficient bucket capacity
• Skew in the distribution of records. This can occur due to two
reasons:
▪ Multiple records have the same search-key value
▪ Chosen hash function produces a non-uniform distribution of key
values
▪ Although the probability of bucket overflow can be reduced, it cannot be
eliminated; it is handled by using overflow buckets.
©Silberschatz, Korth and Sudarshan9.49Database System Concepts - 7th Edition
Handling of Bucket Overflows (Cont.)
▪ Overflow chaining – the overflow buckets of a given bucket are chained
together in a linked list.
▪ Above scheme is called closed addressing (also called closed hashing
or open hashing depending on the book you use)
• An alternative, called
open addressing
(also called
open hashing or
closed hashing
depending on the
book you use) which
does not use overflow
buckets, is not
suitable for database
applications.
©Silberschatz, Korth and Sudarshan9.51Database System Concepts - 7th Edition
Example of Hash File Organization
Hash file organization of instructor file, using dept_name as key.
©Silberschatz, Korth and Sudarshan9.52Database System Concepts - 7th Edition
Deficiencies of Static Hashing
▪ In static hashing, function h maps search-key values to a fixed set of B of
bucket addresses. Databases grow or shrink with time.
• If the initial number of buckets is too small, and the file grows,
performance will degrade due to too many overflows.
• If space is allocated for anticipated growth, a significant amount of
space will be wasted initially (and buckets will be underfull).
• If the database shrinks, again space will be wasted.
▪ One solution: periodic re-organization of the file with a new hash function
• Expensive, disrupts normal operations
▪ Better solution: allow the number of buckets to be modified dynamically.
©Silberschatz, Korth and Sudarshan9.53Database System Concepts - 7th Edition
Dynamic Hashing
▪ Periodic rehashing
• If the number of entries in a hash table becomes (say) 1.5 times the
size of the hash table,
▪ Create a new hash table of size (say) 2 times the size of the
previous hash table
▪ Rehash all entries to the new table
▪ Linear Hashing
• Do rehashing in an incremental manner
▪ Extendable Hashing
• Tailored to disk-based hashing, with buckets shared by multiple hash
values
• Doubling of # of entries in the hash table, without doubling # of
buckets
©Silberschatz, Korth and Sudarshan9.54Database System Concepts - 7th Edition
Comparison of Ordered Indexing and Hashing
▪ Cost of periodic re-organization
▪ Relative frequency of insertions and deletions
▪ Is it desirable to optimize average access time at the expense of worstcase
access time?
▪ Expected type of queries:
• Hashing is generally better at retrieving records having a specified
value of the key.
• If range queries are common, ordered indices are to be preferred
▪ In practice:
• PostgreSQL supports hash indices but discourages use due to poor
performance
• Oracle supports static hash organization, but not hash indices
• SQLServer supports only B+-trees
©Silberschatz, Korth and Sudarshan9.55Database System Concepts - 7th Edition
Multiple-Key Access
▪ Use multiple indices for certain types of queries.
▪ Example:
select ID
from instructor
where dept_name = “Finance” and salary = 80000
▪ Possible strategies for processing queries using indices on single
attributes:
1. Use index on dept_name to find instructors with department name
Finance; test salary = 80000
2. Use index on salary to find instructors with a salary of $80000; test
dept_name = “Finance”.
3. Use dept_name index to find pointers to all records pertaining to the
“Finance” department. Similarly use index on salary. Take the
intersection of both sets of pointers obtained.
©Silberschatz, Korth and Sudarshan9.56Database System Concepts - 7th Edition
Indices on Multiple Keys
▪ Composite search keys are search keys containing more than one
attribute
• E.g., (dept_name, salary)
▪ Lexicographic ordering: (a1, a2) < (b1, b2) if either
• a1 < b1, or
• a1=b1 and a2 < b2
©Silberschatz, Korth and Sudarshan9.57Database System Concepts - 7th Edition
Indices on Multiple Attributes
▪ With the where clause
where dept_name = “Finance” and salary = 80000
the index on (dept_name, salary) can be used to fetch only records that
satisfy both conditions.
• Using separate indices is less efficient — we may fetch many
records (or pointers) that satisfy only one of the conditions.
▪ Can also efficiently handle
where dept_name = “Finance” and salary < 80000
▪ But cannot efficiently handle
where dept_name < “Finance” and balance = 80000
• May fetch many records that satisfy the first but not the second
condition
Suppose we have an index on combined search-key
(dept_name, salary).
©Silberschatz, Korth and Sudarshan9.58Database System Concepts - 7th Edition
Creation of Indices
▪ Example
create index takes_pk on takes (ID,course_ID, year, semester, section)
drop index takes_pk
▪ Most database systems allow specification of type of index, and
clustering.
▪ Indices on primary key created automatically by all databases
• Why?
▪ Some databases also create indices on foreign key attributes
• Why might such an index be useful for this query:
▪ takes ⨝ σname='Shankar' (student)
▪ Indices can greatly speed up lookups, but impose cost on updates
• Index tuning assistants/wizards supported on several databases to
help choose indices, based on query and update workload
©Silberschatz, Korth and Sudarshan9.59Database System Concepts - 7th Edition
Index Definition in SQL
▪ Create an index
create index <index-name> on <relation-name>
(<attribute-list>)
E.g.,: create index b-index on branch(branch_name)
▪ Use create unique index to indirectly specify and enforce the condition
that the search key is a candidate key.
• Not really required if SQL unique integrity constraint is supported
▪ To drop an index
drop index <index-name>
▪ Most database systems allow specification of type of index, and
clustering.
©Silberschatz, Korth and Sudarshan9.60Database System Concepts - 7th Edition
Spatial and Temporal Indices
©Silberschatz, Korth and Sudarshan9.61Database System Concepts - 7th Edition
Spatial Data
▪ Databases can store data types such as lines, polygons, in addition to
raster images
• allows relational databases to store and retrieve spatial information
• Queries can use spatial conditions (e.g. contains or overlaps).
• queries can mix spatial and nonspatial conditions
▪ Nearest neighbor queries, given a point or an object, find the nearest
object that satisfies given conditions.
▪ Range queries deal with spatial regions. e.g., ask for objects that lie
partially or fully inside a specified region.
▪ Queries that compute intersections or unions of regions.
▪ Spatial join of two spatial relations with the location playing the role of join
attribute.
©Silberschatz, Korth and Sudarshan9.62Database System Concepts - 7th Edition
Indexing of Spatial Data
▪ k-d tree - early structure used for
indexing in multiple dimensions.
▪ Each level of a k-d tree partitions the
space into two.
• Choose one dimension for
partitioning at the root level of the
tree.
• Choose another dimensions for
partitioning in nodes at the next
level and so on, cycling through the
dimensions.
▪ In each node, approximately half of the
points stored in the sub-tree fall on one
side and half on the other.
▪ Partitioning stops when a node has less
than a given number of points.
3 1 3
2
3 3
2
▪ The k-d-B tree extends the k-d
tree to allow multiple child
nodes for each internal node;
well-suited for secondary
storage.
©Silberschatz, Korth and Sudarshan9.63Database System Concepts - 7th Edition
Division of Space by Quadtrees
▪ Each node of a quadtree is associated with a rectangular region of space;
the top node is associated with the entire target space.
▪ Each non-leaf nodes divides its region into four equal sized quadrants
• correspondingly each such node has four child nodes corresponding
to the four quadrants and so on
▪ Leaf nodes have between zero and some fixed maximum number of
points (set to 1 in example).
©Silberschatz, Korth and Sudarshan9.64Database System Concepts - 7th Edition
R-Trees
▪ R-trees are a N-dimensional extension of B+-trees, useful for indexing sets
of rectangles and other polygons.
▪ Supported in many modern database systems, along with variants like R+ trees
and R*-trees.
▪ Basic idea: generalize the notion of a one-dimensional interval associated
with each B+ -tree node to an
N-dimensional interval, that is, an N-dimensional rectangle.
▪ Will consider only the two-dimensional case (N = 2)
• generalization for N > 2 is straightforward, although R-trees work well
only for relatively small N
▪ The bounding box of a node is a minimum sized rectangle that contains
all the rectangles/polygons associated with the node
• Bounding boxes of children of a node are allowed to overlap
©Silberschatz, Korth and Sudarshan9.65Database System Concepts - 7th Edition
Example R-Tree
▪ A set of rectangles (solid line) and the bounding boxes (dashed line) of the
nodes of an R-tree for the rectangles.
▪ The R-tree is shown on the right.
©Silberschatz, Korth and Sudarshan9.66Database System Concepts - 7th Edition
Search in R-Trees
▪ To find data items intersecting a given query point/region, do the following,
starting from the root node:
• If the node is a leaf node, output the data items whose keys intersect
the given query point/region.
• Else, for each child of the current node whose bounding box intersects
the query point/region, recursively search the child
▪ Can be very inefficient in worst case since multiple paths may need to be
searched, but works acceptably in practice.
©Silberschatz, Korth and Sudarshan9.67Database System Concepts - 7th Edition
Indexing Temporal Data
▪ Temporal data refers to data that has an associated time period (interval)
• Example: a temporal version of the course relation
▪ Time interval has a start and end time
• End time set to infinity (or large date such as 9999-12-31) if a tuple is
currently valid and its validity end time is not currently known
▪ Query may ask for all tuples that are valid at a point in time or during a
time interval
• Index on valid time period speeds up this task
©Silberschatz, Korth and Sudarshan9.68Database System Concepts - 7th Edition
Indexing Temporal Data (Cont.)
▪ To create a temporal index on attribute a:
• Use spatial index, such as R-tree, with attribute a as one dimension,
and time as another dimension
▪ Valid time forms an interval in the time dimension
• Tuples that are currently valid cause problems, since the value is
infinite or very large
▪ Solution: store all current tuples (with the end time as infinity) in a
separate index, indexed on (a, start-time)
• To find tuples valid at a point in time t in the current tuple index,
search for tuples in the range (a, 0) to (a,t)
▪ Temporal index on primary key can help enforce the temporal primary key
constraint
©Silberschatz, Korth and Sudarshan9.69Database System Concepts - 7th Edition
End of Chapter 9
©Silberschatz, Korth and Sudarshan9.70Database System Concepts - 7th Edition
Example of Hash Index
hash index on instructor, on attribute ID