Even moderately-sized databases cannot be stored entirely within memory (i.e., RAM), which necessitates the need for direct access to records. Like the index of a book, a database index maps keys (e.g., a student id) to the corresponding record. Unfortunately, a “simple linear index” is rarely practical so modern database management systems (DBMSs) use B+ trees and hash indexes to maximize performance.

Learning Objectives

  • Describe the following techniques for locating a record:
    • simple linear index
    • B+ tree
    • hashed file
  • Compare the execution time and storage overhead of the aforementioned techniques
  • Manipulate a B+ tree by inserting and deleting data

How to Complete this Lesson

Complete the following learning activities: (2.5–2.75 hours total)

  1. Read Fundamentals of Database Management Systems Chapter 8: Physical Database Design (60 minutes)
  2. Attend the class meeting (60 minutes)
  3. Complete the handout on B+ trees (30–45 minutes)

Resources