01 — Lecture context: indexes vs. filters

Where this lecture sits

Course logistics: Project 1 (buffer pool) due that Sunday, a profiling/perf + flame-graph recording was published, Homework 3 releases on the 25th, midterm on October 9th covering material through lecture 10 0:52 1:27.
Project 2 is a B+Tree, built from the material of this lecture 7:15.
Recap of the previous lecture: hash tables give average O(1) lookup, but they are used mostly for internal DBMS bookkeeping during query and transaction execution, not as user-facing indexes 3:21 3:50.
- Exception: some systems are essentially just a hash table exposed to users — Redis is roughly that 4:17.
- When you write CREATE INDEX in most systems, you get a B+Tree, not a hash index 3:50.

	Index	Filter
Answers	"where is key K?"	"does key K exist?" (set membership)
Precision	exact location (tuple / small set of tuples)	probabilistic: "probably yes" or "definitely no"
Example	B-Tree / B+Tree	Bloom filter
Declared by	a human, explicitly (`CREATE INDEX`)	usually internal; some systems let you declare them

An index is a data structure built over some subset (or all) of a table's attributes, kept organized/sorted so lookups find a single tuple quickly 4:59 5:09.
- Not always a single tuple: Postgres indexes can return blocks of tuples 5:09.
A filter answers set-membership queries — it tells you a key probably exists, but never where it is; the canonical example is the Bloom filter, covered in a later lecture 5:24 6:01.
Bloom filters can be declared on tables in some systems for query optimization, but they are usually an internal structure 6:01.

Anything in the table must be reflected in its indexes and filters, otherwise lookups produce false negatives 6:27 6:55.
Keeping indexes synchronized and thread-safe under concurrent access is the subject of the following lecture 6:27.