Suggest an editImprove this articleRefine the answer for “How are indexes implemented inside a DBMS?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)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 are used - most often **B-trees**, less often hash tables, GiST, GIN, or R-trees. **Key point:** B-tree/B+tree is the main type (PostgreSQL, MySQL InnoDB, Oracle) with `O(log n)` search; hash indexes give `O(1)` for exact matches but don't support ranges; GiST and GIN are used for full-text search, JSON, and arrays; R-tree is used for geospatial data.Shown above the full answer for quick recall.Answer (EN)ImageIndexes 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.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.