Database Indexing: Types and Internals

Question: What is a database index? What types of indexes exist, what underlying data structures do they use, and what are their trade-offs?

Answer framing: An index is a data structure that improves the speed of data retrieval at the cost of extra storage and slower writes. Common types: B-tree/B+tree indexes (the default in most RDBMSs, good for range queries and equality, O(log n) lookups), hash indexes (O(1) average lookup for equality only, no range query support), and bitmap indexes (efficient for low-cardinality columns). Trade-offs: indexes speed up SELECT/read queries but add overhead to INSERT/UPDATE/DELETE since the index structure must also be maintained; over-indexing a table can hurt write-heavy workloads.