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

  1. Read Fundamentals of Database Management Systems Chapter 8: Physical Database Design (60 minutes)
  2. Watch Overview of Indexing (9 minutes)
  3. Read the handout on B+ trees but do not attempt the practice exercises (5 minutes)
  4. Watch B+ Trees Basics 1 (4 minutes)
  5. Watch B+ Trees Basics 2 (9 minutes)
  6. Re-read the handout on B+ trees and complete the practice exercises (30–45 minutes)
  7. Watch B+ Tree Basics 3 (6 minutes)
  8. Recommended: Complete the optional homework on physical database design (45 minutes)
  9. Complete the short answer portion of the B+ tree assignment (30–45 minutes)
    • Be sure to read the instructions for the entire assignment before starting
« Project Work Day I ACID Properties »