Database and Indexing Algorithms

10-page quick guide for scans, indexes, joins, sorting, optimization, and transactions.

Purpose: a compact 10-page study guide for students who want to recognize, choose, and implement common
algorithm ideas.
How to use it: read one page, trace the example, then solve the quick practice before moving on.

Symbol Meaning

n input size: number of items, characters, nodes, or records

O(...) upper-bound growth rate used to compare algorithms

stable keeps equal items in their original relative order

in-place uses only small extra memory beyond the input array

Database and Indexing Algorithms Page 1

 1. Algorithms Inside Databases
Databases depend on algorithms for finding, sorting, joining, indexing, caching, and recovering data.
Understanding them helps you write faster queries.

- A database table may contain millions of rows, so scanning everything can be too slow.
- Indexes are data structures that speed up searching.
- Query optimizers choose execution plans based on estimated cost.
- The best SQL query is often the one that lets the database use a good algorithm.

Database task Algorithm idea

lookup by key B-tree or hash index

sort result external merge sort

join tables nested loop, hash join, merge join

transaction safety logging and recovery algorithms

Quick practice
- Why is a full table scan slow on a huge table?
- What does an index help with?

Database and Indexing Algorithms Page 2

 2. Full Scan vs Index Lookup
A full scan checks many or all rows. An index lookup jumps to likely locations, like using a book index instead of
reading every page.

- Full scan can be fine for small tables or queries that need most rows.
- Index lookup is faster when the filter is selective.
- Using a function on an indexed column can prevent index use in some databases.
- Indexes speed up reads but slow down writes because the index must be updated.

Method When useful

full table scan small table or most rows needed

index seek specific key or selective range

covering index index contains all needed columns

bitmap index some analytic workloads

Quick practice
- Which is better for WHERE id = 100?
- Why might an index not help when selecting 90% of a table?

Database and Indexing Algorithms Page 3

 3. B-Tree Index
B-trees keep keys sorted in a balanced tree with many keys per node. They are excellent for disk and SSD
storage because each node read brings many keys.

- Search, insert, and delete are O(log n).

- The tree stays balanced, so path lengths remain short.
- B-trees support equality search and range queries.
- Most relational database indexes are based on B-tree-like structures.
# Conceptual search:
# start at root
# choose the child range containing the key
# repeat until leaf
# return matching record pointer or not found

Quick practice
- Why does a B-tree support ORDER BY well?
- Why are wide nodes useful for disk pages?

Database and Indexing Algorithms Page 4

 4. Hash Index
A hash index uses a hash function to map a key to a bucket. It is strong for equality lookup but weak for ordered
range queries.

- Average lookup can be O(1).

- Collisions must be handled by chaining, probing, or bucket pages.
- Hash indexes do not keep keys in sorted order.
- They are a poor choice for WHERE value BETWEEN a AND b.

Operation Hash index fit

id = 123 excellent

name starts with A poor without special support

price between 10 and 20 poor

exact token lookup good

Quick practice
- Why is hash index not good for sorting?
- Give one equality query that fits a hash index.

Database and Indexing Algorithms Page 5

 5. Sorting Large Data
Databases may sort data larger than memory. External merge sort breaks data into sorted runs, then merges
them from disk.

- First, sort chunks that fit in memory.

- Write sorted runs to disk.
- Merge runs using buffers and priority queues.
- An index may avoid sorting if it already stores rows in the needed order.
# External merge sort idea:
# 1. read memory-sized chunks
# 2. sort each chunk and write a run
# 3. merge the runs into final order

Quick practice
- Why can normal in-memory sort fail for huge data?
- How can an index help ORDER BY?

Database and Indexing Algorithms Page 6

 6. Join Algorithms
A join combines rows from two tables. Different join algorithms work best for different sizes, indexes, and sort
orders.

- Nested loop join is simple and good when one side is small or indexed.
- Hash join builds a hash table from one side, then probes it with the other side.
- Merge join works when both inputs are sorted by the join key.
- The query optimizer estimates which join is cheapest.

Join Good when

nested loop outer table small or inner index exists

hash join large unsorted equality join

merge join both sides sorted by join key

cross join rare; produces all combinations

Quick practice
- Which join fits two large unsorted tables joined by equality?
- Why can merge join be fast on sorted inputs?

Database and Indexing Algorithms Page 7

 7. Query Optimization
A query optimizer searches for a good execution plan. It considers indexes, join order, estimated row counts, and
operation costs.

- The same SQL can be executed in many different ways.

- Join order can change performance dramatically.
- Statistics help estimate how many rows a filter will return.
- EXPLAIN plans show the chosen strategy, such as scan, seek, hash join, or sort.

Optimizer input Why it matters

table size affects scan and join cost

statistics predicts selectivity

indexes provides faster access paths

memory affects sorting and hashing

Quick practice
- Why might outdated statistics cause a poor plan?
- What does EXPLAIN help you inspect?

Database and Indexing Algorithms Page 8

 8. Transactions and Logging
Databases use algorithms to make transactions reliable, even if power fails during a write.

- ACID means atomicity, consistency, isolation, and durability.

- Write-ahead logging records changes before applying them permanently.
- Recovery can redo committed changes and undo incomplete ones.
- Locking and MVCC are strategies for safe concurrent access.

Term Meaning

commit make a transaction durable

rollback undo a transaction

write-ahead log record needed recovery information first

MVCC readers can see a consistent snapshot

Quick practice
- Why should the log be written before data pages?
- What problem does rollback solve?

Database and Indexing Algorithms Page 9

 9. Practical Indexing Rules
Indexing is an algorithm design choice for your database. Too few indexes make reads slow; too many make
writes and storage expensive.

- Index columns often used in WHERE, JOIN, ORDER BY, or GROUP BY.
- Composite indexes depend on column order.
- Avoid indexing every column automatically.
- Measure with real queries and EXPLAIN rather than guessing.
-- Example idea:
-- WHERE customer_id = ? AND order_date >= ?
-- A composite index on (customer_id, order_date)
-- may support this filter efficiently.

Quick practice
- Which columns would you consider indexing in an orders table?
- Why can too many indexes slow INSERT operations?

Database and Indexing Algorithms Page 10