Indexing and B+ trees

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)

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

Resources

Overview of Indexing (9 minutes)
B+ Trees Basics 1 (4 minutes)
B+ Trees Basics 2 (9 minutes)
B+ Tree Basics 3 (6 minutes)
Questions for physical database design (45 minutes)