Search⌘ K
Home
Courses
Deep Dive into the Internals of the Database

Hash Index

Explore the hash index, a crucial data structure in databases that provides efficient key-value lookups. Understand how in-memory HashMaps and disk-resident storage segments work together to handle inserts, reads, updates, and deletes. Discover the importance of compaction for managing storage and the role of hash indexes in recovery. Learn the benefits and limitations of hash indexes for database operations.

We'll cover the following...

Introduction

A hash index is a widely used basic data structure that provides fast key-value lookups. A hash index is comparable to a dictionary or a hashmap in programming languages, where the key acts as a lookup index pointing to the location where the value is stored. The search and insertion time complexity of hash index is always O(1)O(1).

Many databases use the hash index as auxiliary storage structures for lookup operations with other data structures such as B+ tree. As a result, hash indexes are used in databases like MySQL and Postgresql.

Data structure

Hash indexes have two primary data structures:

  • In-memory HashMap

  • Disk-resident ...