Page 188 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 8: B-trees

Notes

Task Consider the following binary search tree:
a

b

g

f

c

e

d

Splay this tree at each of the following keys in turn:
d b g f a d b d

8.8 Applications

1. Databases: A database is a collection of data organized in a fashion that facilitates updating,
retrieving, and managing the data. The data can consist of anything, including, but not
limited to names, addresses, pictures, and numbers. Databases are commonplace and are
used everyday. For example, an airline reservation system might maintain a database of

available flights, customers, and tickets issued. A teacher might maintain a database of
student names and grades.
Because computers excel at quickly and accurately manipulating, storing, and retrieving
data, databases are often maintained electronically using a database management system.
Database management systems are essential components of many everyday business
operations. Database serve as a foundation for accounting systems, inventory systems,
medical recordkeeping sytems, airline reservation systems, and countless other important
aspects of modern businesses.

It is not uncommon for a database to contain millions of records requiring many gigabytes
of storage. In order for a database to be useful and usable, it must support the desired
operations, such as retrieval and storage, quickly. Because databases cannot typically be
maintained entirely in memory, b-trees are often used to index the data and to provide
fast access. For example, searching an unindexed and unsorted database containing n key
values will have a worst case running time of O(n); if the same data is indexed with a b-tree,
the same search operation will run in O(log n). To perform a search for a single key on a set
of one million keys (1,000,000), a linear search will require at most 1,000,000 comparisons.
If the same data is indexed with a b-tree of minimum degree 10, 114 comparisons will
be required in the worst case. Clearly, indexing large amounts of data can signifi cantly
improve search performance. Although other balanced tree structures can be used, a b-tree
also optimizes costly disk accesses that are of concern when dealing with large data sets.

LOVELY PROFESSIONAL UNIVERSITY 183