How are indexes implemented inside a DBMS?

Indexes inside a DBMS are implemented as separate data structures optimized for fast search, sorting, and navigation. Depending on the index type and storage engine, different algorithms get used - most often B-trees, less often hash tables, GiST, GIN, or R-trees.

Let's break it down:

#1. B-tree / B+tree (the main type)

The most common variant (PostgreSQL, MySQL InnoDB, Oracle).

• Tree nodes hold keys and references to child nodes.
• Keys are sorted, so search, insert, and delete take O(log n) operations.
• Leaf nodes are linked to each other, which speeds up range queries (BETWEEN, <, >, ORDER BY).

Example: an index on age stores a tree where nodes hold age ranges. Finding a 25-year-old user takes 3-4 levels from root to leaf, instead of scanning the whole table.

#2. Hash indexes

Used when you need exact matches (=), not ranges.

• The key runs through a hash function that determines a "bucket".
• The bucket stores a reference to the table row.
• Lookups are very fast (O(1)), but you can't use them for sorting or > / <.

Example: PostgreSQL supports USING hash, but it's used less often due to its limitations.

#3. GiST (Generalized Search Tree)

A flexible structure that can store not just numbers and text, but also geodata, arrays, ranges, and the like. Used, for example, in PostgreSQL for FULL TEXT SEARCH, cube, hstore, tsvector.

#4. GIN (Generalized Inverted Index)

Optimized for searching sets: arrays, JSON, text.

• Stores "inverted lists", for each value or word it lists which rows it appears in.
• Used in full-text search (to_tsvector, @@).

#5. R-tree (for geodata)

Used in engines like SQLite or PostGIS to store coordinates. Indexes spatial objects, points, polygons, rectangles, and speeds up queries like "find all objects within a radius".

The general structure of an index file:

• Metadata (index type, tree depth, statistics).
• Nodes (branches) and leaves (keys + references to rows).
• In a DBMS cluster, a separate physical page (usually 8 KB).

Summary: An index is a built-in data structure inside the DBMS, usually implemented as a B+tree. It stores sorted keys and references to rows to provide fast search (O(log n)) and efficient filters, sorts, and ranges.