PHYSICAL DATABASE DESIGN - Fundamentals of Database Management Systems - page 211

Index Salesperson File

Salesperson Record Record Salesperson Salesperson

Name Address Number Number Name City

Adams 3 1 119 Taylor New York

Baker 2 2 137 Baker Detroit

Carlyle 6 3 186 Adams Dallas

Dickens 4 4 204 Dickens Dallas

Green 7 5 255 Lincoln Atlanta

Lincoln 5 6 361 Carlyle Detroit

F I G U R E 8.13
Salesperson file with the insertion of a
record for #452 French. But how can you
squeeze the index record into the proper
sequence?

Taylor 1 7 420 Green Tucson

8 452 French New York

?

French 8

Indeed, the simple linear index is not a good solution for indexing the records
of a file. This leads us to another kind of index that is suitable for indexing even
very large files, the B + -tree index.

B -Tree Index The B + -tree index, in its many variations (and there are many,

including one called the B*-tree), is far and away the most common data-indexing
system in use today. Assume that the Salesperson File now includes records for
several hundred salespersons. Figure 8.14 is a variation of how the B

+

-tree index
works. The figure shows the salesperson records arranged in sequence by the
Salesperson Number field on ten cylinders (numbered 1-10) of a disk. Above the
ten cylinders is an arrangement of special index records in what is known as a
''tree.'' There is a single index record, known as the ''root,'' at the top, with
''branches'' leading down from it to other ''nodes.'' Sometimes the lowest-level
nodes are called ''leaves.'' For the terminology, think of it as a real tree turned
upside-down with the roots clumped into a single point at the top, Figure 8.15.

+

8.1 S IMPLE L INEAR I NDEXES

YOUR

TURN

W hen we think of indexes (other than
those used to access data in computers), most people
would agree that those thoughts would be limited to the
indexes in the backs of books. But, if we want to and
it makes sense, we can create indexes to help us find
objects in our world other than items inside books. (By
the way, have you ever seen a directory in a department
store that lists its departments alphabetically and then,
next to each department name, indicates the floor it's on?
That's an index, too!)

Q UESTION :
Choose a set of objects in your world and develop a
simple linear index to help you find them when you
need to. For example, you may have CDs or DVDs on
different shelves of a bookcase or in different rooms
of your house. In this example, what would be the
identifier in the index for each CD or DVD? What
would be the physical location in the index? Think
of another set of objects and develop an index for
them.