FREE DATABASE COURSE / SIX ENGINES

Database Indexing Course: Algorithms and Index Types Explained

Understand database indexes from the ground up with six platform guides, illustrated search algorithms, practical SQL/CQL examples, trade-offs, and query-plan checks. Learn when to use each type and when not to, with a beginner-friendly, query-first approach.

What Is a Database Index?

A database index is an extra data structure that helps locate records for a query. It is similar to a book index: rather than reading every page, the reader follows a value to a smaller set of likely locations. Indexes speed up some reads but require storage and extra work for inserts, updates, and deletes.

How a B-tree Index Search Algorithm Works

A B-tree stores keys in sorted leaves and branch nodes containing separators. A search compares its key at each level, chooses one child, and repeats until it reaches a matching leaf entry. The tree stays balanced so lookups do not scan every key.

B-tree algorithm: compare a requested key at branch nodes, narrow to the matching leaf range, and follow a row pointer
Step-by-step B-tree lookup: compare separators, follow one branch, find the leaf key, then fetch the row.

Hash Index Lookup Algorithm

A hash index transforms an exact key into a bucket number. It can be effective for equality lookups, but hashing does not preserve value order, so it cannot naturally answer a range such as ?between 20 and 50.?

Hash lookup algorithm maps an exact search key through a hash function to a bucket of candidate rows
Hashing maps equal keys to a bucket; collisions still require checking stored keys.

Inverted Index and Full-Text Search Algorithm

An inverted index maps each term or component value to a list of records containing it. Search can find documents by term without scanning every document, then combine posting lists for multi-term queries.

Inverted-index algorithm maps terms such as apple and red to lists of matching row IDs
Term-to-row posting lists power text search and some array or JSON membership indexes.

LSM-tree and Distributed Database Indexing

Log-structured merge designs buffer writes, flush sorted immutable files, and compact them in the background. Reads may consult memory and multiple files. Cassandra also routes primary-key queries by partition tokens, so index choices do not remove distributed-data modeling.

LSM-tree write path: memory table flushes to sorted files and background compaction merges levels
Conceptual LSM write/read path; actual storage details differ by engine and release.

Spatial Index Search with Trees and Regions

Spatial indexes group nearby values into bounding regions or cells. A query checks regions that intersect the requested area and skips regions that cannot contain a result.

Spatial search algorithm checks intersecting regions and skips regions outside a query area
Spatial index example: prune non-overlapping regions before exact geometry checks.

Bitmap Index Algorithm for Combining Filters

Bitmap indexes represent matching row positions as bits. Boolean operations such as AND and OR can combine several filters before retrieving the matching rows; they are commonly suited to read-heavy analytical patterns rather than high-concurrency row updates.

Bitmap algorithm represents predicate matches as bit vectors and intersects them to identify rows
Bitmap illustration: intersect bit vectors to find rows satisfying both conditions.

Compare Index Types Across Database Systems

PostgreSQL provides multiple access methods; MongoDB has specialized document index types; Cassandra prioritizes partition-key routing and SAI; MySQL depends on storage engine; Oracle includes B-tree/bitmap/domain options; SQL Server adds rowstore, columnstore, and specialized structures.

Choose an Index from the Query Pattern

Start with actual filters, range boundaries, sorts, joins, and output columns. Equality and range needs differ from full-text terms, array membership, geospatial containment, or analytical scans. Choose the smallest structure that supports a measured workload.

How Indexes Affect Reads and Writes

Indexes can reduce rows or pages examined, but a low-selectivity query may still use a scan. Every maintained index adds storage and write work. Specialized structures may generate several entries for one row or maintain separate background processes.

How to Check an Index Execution Plan

Use the platform's explain/actual-plan tools. Compare estimated and actual rows, keys examined, rows fetched, partitions visited, sorts, rechecks, buffer reads, and elapsed time. Test representative data and concurrent writes before calling a change an improvement.

Common Database Indexing Mistakes

  • Adding an index to every searchable column.
  • Ignoring composite key order and query operators.
  • Assuming index presence means the optimizer uses it.
  • Benchmarking only reads and ignoring write amplification and storage.
  • Copying syntax or features across engines without checking version support.

Database Index Course Roadmap

Begin with the algorithm diagrams, then open the database guide matching your engine. Each index-type page has at least ten focused headings covering the definition, algorithm, query fit, creation example, performance costs, limitations, verification, and official references.

  1. PostgreSQL index types and examples
  2. MongoDB index types and examples
  3. Apache Cassandra index types and examples
  4. MySQL index types and examples
  5. Oracle Database index types and examples
  6. Microsoft SQL Server index types and examples

PostgreSQL Index Types: Complete Guide Directory

Open an individual PostgreSQL guide for algorithm diagrams, SQL/CQL examples, query fit, limitations, and tuning advice.

  1. Bloom Extension Indexes
  2. BRIN Block Range Indexes
  3. B-tree Indexes
  4. Expression Indexes
  5. GIN Inverted Indexes
  6. GiST Indexes
  7. Hash Indexes
  8. Covering Indexes with INCLUDE
  9. Multicolumn Indexes
  10. Partial Indexes
  11. SP-GiST Indexes
  12. Unique and Exclusion Indexes

MongoDB Index Types: Complete Guide Directory

Open an individual MongoDB guide for algorithm diagrams, SQL/CQL examples, query fit, limitations, and tuning advice.

  1. 2d Geospatial Indexes
  2. 2dsphere Geospatial Indexes
  3. Clustered Collections and Indexes
  4. Collation-Aware Indexes
  5. Compound Indexes
  6. Hashed Indexes
  7. Hidden Indexes
  8. Multikey Indexes
  9. Partial Indexes
  10. Single-Field Indexes
  11. Sparse Indexes
  12. Text Indexes
  13. TTL Expiration Indexes
  14. Unique Indexes
  15. Vector Search Indexes
  16. Wildcard Indexes

Apache Cassandra Index Types: Complete Guide Directory

Open an individual Apache Cassandra guide for algorithm diagrams, SQL/CQL examples, query fit, limitations, and tuning advice.

  1. ALLOW FILTERING and Index Alternatives
  2. Clustering Columns and Order
  3. Indexes on Collections
  4. Custom Index Implementations
  5. Materialized Views as a Query Alternative
  6. Partition Keys
  7. Primary-Key Indexing and Query Routing
  8. Storage-Attached Indexing (SAI)
  9. SASI Indexes (Legacy)
  10. Traditional Secondary Indexes (2i)
  11. Storage-Attached Vector Indexes

MySQL Index Types: Complete Guide Directory

Open an individual MySQL guide for algorithm diagrams, SQL/CQL examples, query fit, limitations, and tuning advice.

  1. InnoDB B-tree Indexes
  2. InnoDB Clustered Primary Indexes
  3. Composite and Covering Indexes
  4. FULLTEXT Indexes
  5. Functional Indexes
  6. Invisible Indexes
  7. Multi-Valued JSON Indexes
  8. MEMORY Hash Indexes
  9. Partitioned Table Indexes
  10. Prefix Indexes
  11. InnoDB Secondary Indexes
  12. Spatial Indexes
  13. Unique and Primary Indexes

Oracle Database Index Types: Complete Guide Directory

Open an individual Oracle Database guide for algorithm diagrams, SQL/CQL examples, query fit, limitations, and tuning advice.

  1. Bitmap Join Indexes
  2. Bitmap Indexes
  3. B-tree Indexes
  4. Composite and Descending Indexes
  5. Prefix-Compressed Indexes
  6. Domain Indexes
  7. Function-Based Indexes
  8. Global Partitioned Indexes
  9. Invisible Indexes
  10. Index-Organized Tables (IOTs)
  11. Local Partitioned Indexes
  12. Reverse-Key Indexes

Microsoft SQL Server Index Types: Complete Guide Directory

Open an individual Microsoft SQL Server guide for algorithm diagrams, SQL/CQL examples, query fit, limitations, and tuning advice.

  1. Clustered Rowstore Indexes
  2. Columnstore Indexes
  3. Filtered Indexes
  4. Full-Text Indexes
  5. Indexed Views
  6. JSON Property Indexes with Computed Columns
  7. Memory-Optimized Hash Indexes
  8. Nonclustered and Included-Column Indexes
  9. Partitioned Indexes
  10. Spatial Indexes
  11. Unique Indexes
  12. XML Indexes

Database Indexing Questions

Which index is fastest?

There is no universal fastest index. The correct choice depends on operators, data distribution, selectivity, storage engine, cache, and write rate.

Will more indexes improve SEO or database speed?

Indexing a website page and indexing database rows are different ideas. Extra database indexes do not guarantee faster queries; every index should be measured against a real query.

Official Database Index References