Indexing Internals: B-Trees, Hash & Bitmap Indexes

-- A B-tree index keeps the indexed values in SORTED order,
-- so the database can binary-search them instead of reading
-- every row. This is the default in PostgreSQL, MySQL, SQLite...
CREATE INDEX idx_employees_salary
ON employees (salary);

-- Now an equality lookup walks down the tree (a few hops),
-- instead of scanning all 1,000,000 rows:
SELECT id, name, salary
FROM employees
WHERE salary = 75000;

-- A range scan finds the FIRST matching leaf, then walks the
-- sorted leaves left-to-rig
...

-- Ask the planner what it would do (this text is the EXPLAIN
-- "plan" — read it bottom-up; the deepest node runs first):
EXPLAIN
SELECT id, name, salary FROM employees WHERE salary = 75000;

-- ✅ Expected plan (uses the index we just created):
--   Index Scan using idx_employees_salary on employees
--     Index Cond: (salary = 75000)
--
-- "Index Scan" = good — it jumped straight to the rows.
-- If you instead see "Seq Scan on employees", the index was
-- NOT used and every row was read one by
...

-- A HASH index stores hash(value) -> row location in buckets.
-- Lookup is O(1) average for EQUALITY, but the hash destroys
-- ordering, so it can do = and nothing else.
CREATE INDEX idx_users_email_hash
ON users USING hash (email);

-- ✅ Great — exact match jumps to one bucket:
SELECT * FROM users WHERE email = 'alice@example.com';

-- ❌ A hash index CANNOT serve any of these (no order exists):
--   WHERE email > 'a'          -- no range scan
--   WHERE email LIKE 'alice%'  -- no prefix search
...

-- A BITMAP index shines on LOW-CARDINALITY columns — ones with
-- only a handful of distinct values (status, is_active, region).
-- It stores one bit-string per distinct value; bit position N
-- means "row N has this value":
--   status='shipped'   -> 1 0 0 1 1 0 ...
--   status='pending'   -> 0 1 1 0 0 1 ...
-- (Oracle creates these explicitly; PostgreSQL builds them
--  on the fly when combining several B-tree indexes.)
CREATE BITMAP INDEX idx_orders_status ON orders (status);

-- The magic: 
...

-- CLUSTERED index = the table rows are PHYSICALLY stored in the
-- index's order. There can be only ONE per table (rows can only
-- be sorted one way). The primary key is usually the cluster key.
-- A "leaf" of the clustered index IS the full row.
--   (SQL Server: CREATE CLUSTERED INDEX; MySQL/InnoDB clusters
--    on the PRIMARY KEY automatically.)
CREATE CLUSTERED INDEX idx_orders_pk ON orders (order_id);

-- NON-CLUSTERED index = a separate sorted structure whose leaves
-- hold the indexed 
...

-- A COVERING index contains EVERY column a query needs, so the
-- database answers the query from the index alone and never
-- touches the table — an "index-only scan".

-- This query needs customer_id (to filter) and total (to return):
SELECT total FROM orders WHERE customer_id = 42;

-- Put the filter column first, then INCLUDE the payload column:
CREATE INDEX idx_orders_cust_total
ON orders (customer_id) INCLUDE (total);
-- (PostgreSQL/SQL Server use INCLUDE; MySQL just lists both
--  column
...