Intuition The ONE core ideaA table is just a big pile of rows on a disk , and finding one row by reading them all is painfully slow because disk reads are the bottleneck. An index is a second, cleverly-organized copy of one column that lets you jump to the row you want — the whole topic is about which organization (sorted tree, hash bucket, or word-list) makes which kind of jump fast.
Before you can read the parent note, you need to own every symbol and word it throws at you. This page builds each one from nothing, in the order they depend on each other. Nothing here is assumed — if the parent used it, we define it.
Definition Row, table, and the "heap"A row is one record — think one line in a spreadsheet (one person: name, email, age). A table is the whole spreadsheet: many rows stacked. When rows are just dumped one after another with no ordering, that pile is called a heap .
Picture a shoebox stuffed with index cards, one card per person, in the order they walked in the door. That shoebox is the heap. There is no rule about where any card sits.
Look at the figure. To find the card for "email = zara@x.com " you have no shortcut — you pull card 1, check, pull card 2, check... until you hit it or run out. That "check every card" motion is the enemy this whole topic defeats.
N N the number of rows in the table . If the table has a billion rows, N = 1 , 000 , 000 , 000 any table size.
Why we need it: every cost we talk about ("how much work?") is measured as a function of N . A shortcut that saves nothing when N N N
Definition Disk vs memory, page, and I/OMemory (RAM) is the fast scratchpad the CPU works in; it is emptied when power goes off. Disk (a hard drive or SSD) is the slow-but-permanent storage where the table really lives. Data moves between them in fixed chunks called pages (commonly ~8 KB each). One trip to fetch a page from disk is one I/O ("Input/Output" operation).
Intuition WHY we count disk reads and ignore CPUA modern CPU compares millions of values per millisecond — comparing is free . But a spinning disk does only ~100 random page-fetches per second; an SSD maybe ~10,000. So the only cost that matters is: how many pages did we have to drag off the disk? Every "cost" in this topic is a count of page reads, nothing else.
This is why the parent keeps saying "the bottleneck is not CPU, it is disk I/O." Hold onto this: fewer page reads = faster query , full stop. See Disk vs Memory I/O .
Definition Big-O notation,O ( ⋅ ) O ( something ) N O ( N ) N O ( 1 ) N O ( log N ) very slowly — the log of N
Intuition The picture of these three growth ratesImagine three staircases as N O ( N ) O ( log N ) O ( 1 ) O ( N ) O ( log N ) O ( 1 )
See Big-O Notation for the full treatment. For this topic you only need the ordering: O ( 1 ) < O ( log N ) < O ( N ) O ( N )
The parent writes log m N ⌈ log m N ⌉
log b x b h b h logarithm asks the reverse question: "b how many times gives x log b x log b x = h means exactly b h = x
Intuition WHY a logarithm and not something elseA B-tree fans out: one node points to m those points to m h m × m × ⋯ = m h N m h ≥ N h literally "how many times must I multiply m N log m N
Worked example Feeling how slow the log growsWith branching m = 100 log 100 100 = 1 log 100 10 , 000 = 2 log 100 1 , 000 , 000 = 3 one . A billion rows (1 0 9 log 100 1 0 9 = 2 9 = 4.5
Definition The ceiling brackets⌈ ⌉ ⌈ x ⌉ x ⌈ 4.5 ⌉ = 5 ⌈ log m N ⌉
m m how many children one tree node can point to . Because one node is packed into one disk page (~8 KB) and each key+pointer is small, m hundreds . Big m wide and shallow → fewer levels → fewer disk reads. This is the single number that makes B-trees win.
You will meet m B+ Tree Data Structure ; here just remember: large m , and height = number of disk reads.
Definition Key and row-pointerA key is the value you search by — the email, the id, the age: whatever column the index is built on. A row-pointer is a tiny address saying "the full row lives over there on disk." An index entry is the pair (key → row-pointer) : sorted by key so you can find it, plus the address so you can fetch the real row.
Picture the book index at the back: the word is the key, the page number is the pointer. The index is small because it holds only these two things, not the whole rows.
Definition Sorted / orderedSorted means arranged smallest-to-largest (or A→Z). The value of sorting: once things are in order you can (a) find one by "smart guessing" (binary-search style) and (b) grab a range ("everything from 20 to 30") by starting at 20 and walking forward until you pass 30.
Keep this word close: a B-tree keeps keys sorted (so ranges and ORDER BY are cheap), while a hash deliberately throws order away (so it can't do ranges at all). Half the parent's comparison table is just this one distinction.
Definition Hash function and bucketA hash function hash ( k ey ) bucket is one numbered slot in a big array. We pick the slot with
bucket = hash ( k ey ) mod B B mod the remainder after dividing , which wraps the scrambled number into the valid range 0 … B − 1
O ( 1 ) compute its bucket and jump straight there: constant work, O ( 1 ) N 99 100 nowhere to walk — the neighbours aren't neighbours anymore. That single trade-off is why hash is brilliant for = exact and useless for <, >, BETWEEN, ORDER BY.
See Hashing for collisions and bucket details.
These four terms power the full-text section.
Definition The full-text vocabulary
Tokenization = chop a sentence into individual words ("the cat sat" → the, cat, sat).Stemming = cut words down to their root so variants match (running, ran → run).Stop-word removal = throw away ultra-common filler (the, is, a) that helps no search.Postings list = for one word, the sorted list of document IDs that contain it (e.g. sat → {D1, D2}).
Definition Inverted indexA normal index maps document → its words . An inverted index flips that to word → documents . WHY flip: your search gives you a word and asks for the documents — so you want the arrow pointing from word to documents. Answering cat AND dog then becomes intersecting two postings lists (set operations), which is fast because the lists are pre-sorted.
cost = count of disk reads
Big-O growth O(N) O(logN) O(1)
This map is the parent note's skeleton: the left column (rows, pages, cost) is why indexes exist; log m N m B-tree ; the hash function builds the hash index ; the word-tools build the full-text index . Master this page and the parent reads like a story you already know. Related deeper notes: Clustered vs Non-clustered Index , Query Optimization .
Cover the right side and answer each before opening the parent.
What does N The number of rows in the table.
Why do we count disk page reads instead of CPU comparisons? Disk I/O is thousands of times slower than CPU; page reads are the real bottleneck.
Read out loud: O ( 1 ) O ( log N ) O ( N ) Constant (flat), grows very slowly (gentle slope), grows in step with N (steep ramp).
What question does log m N How many times must you multiply m N
Compute log 100 1 0 9 9/2 = 4.5 log 100 x = l o g 10 100 l o g 10 x = 2 9
What does ⌈ 4.5 ⌉ 5
What is m Children per node; large m
What two things are in one index entry? A key (the searched value) and a row-pointer (address of the full row).
Why can a hash index do O ( 1 ) You compute the bucket directly (constant), but hashing scatters order so neighbouring values land far apart.
What does mod B hash ( k ey ) mod B Gives the remainder after dividing, wrapping the hash into a valid bucket number 0.. B − 1
Define an inverted index and why it's "inverted". Maps word → documents (flipping document → words), because a search gives a word and asks for documents.
Name the three text preprocessing steps. Tokenization, stemming, stop-word removal.
