Hash Index

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)$.

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 ...