Database Indexing

This came up in a recent interview, the topic of indexing a database.

While I know it’s a concept that exists, I didn’t have enough knowledge at hand to have a fluent conversation about the topic. This note is an attempt at correcting that, lol.

What is DB indexing

Database indexing is a way to reduce lookup time of a database.

an index maps search keys to corresponding data on disk by using different in-memory & on-disk data structures.

When can I index?

  • You have millions/billions of rows in your tables, & lookup time has become unusable
  • You know your data access patterns

Types of indexes

  • B-tree
  • Function-based
  • BRIN
  • GiST
  • Clustered/Non-clustered index

Related reading