Why the word is the key
The question is words. A key that matches the question is a key that makes the answer one lookup.
The size claim
The index is larger than the library. Larger is honest when the answer is faster, and the trade is written.
The inverted index
The structure is a word pointing at documents. The pointing is the whole engine, and the pointing is what makes an answer independent of the library size.
What you will see
One line with a reason. Larger with a reason is honest.
About 1 min of reading
Try It
Build a posting list
1
Write two postings
printf 'red 0 2 5\nfish 0 1 2\n' > /tmp/p.txt; cat /tmp/p.txt
Before you run it, say out loud what it will print. Then open the answer.
What it prints
Two lines. A word with sorted ids is a posting.
2
Merge two postings
printf '0 2 5\n0 1 2\n' | tr ' ' '\n' | sort -n | uniq | wc -l
Before you run it, say out loud what it will print. Then open the answer.
What it prints
4. Four ids is the union in one walk, which is the linear cost.
3
Write the size trade
printf 'index_bytes 900000 library_bytes 500000 reason=answer-faster\n' > /tmp/s.txt; cat /tmp/s.txt
Before you run it, say out loud what it will print. Then open the answer.
What it prints
One line with a reason. Larger with a reason is honest.
Data Flow
Tokens to a word pointing at ids
1
Each token becomes a key
↓
2
The document id is appended to the posting
↓
3
The postings are sorted
↓
4
The whole map is written to a file
Why this works
Examples
The key is the word
The value is a list of ids. A list of ids is a posting, and a posting is the smallest honest answer.
The list is sorted
Sorted means two lists can be merged in one walk. The walk is the cost, and the cost is linear rather than squared.
The structure is written to a file
Written means it can be read back. Read back means the build and the answer are separate programs.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← Splitting into tokens
Previous Lesson
Splitting into tokens