Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I use the mental model of nested maps for "column order matters". For example, an index "published, low_quality_probability, lang" is just a Map<date, Map<number, Map<lang, rowId>>> in my mental model. These maps are ordered by the order the index possesses. That explains why column order matters and why one cannot skip columns and why it stops at range queries.

Just imagine getting a final rowId from these nested maps and you'll see why the index works for some queries and doesn't for others.



It’s way easier if you think of the indexes as tuple keys in a binary tree.

Because they’re tuple keys in a b-tree. That also explains how ranges work efficiently.


Yeah, if you're going to work with databases regularly I think it's worth learning how b-trees work. It'll make a lot of things much more intuitive.

If you wanna get a very complete grounding in how the big rdbmses work, Andy Pavlo's lectures and class notes are fantastic.


I definitely second Andy Pavlo's lectures.


I use this same approach to explain indexes to database novices; it usually helps a lot, especially with how the leaf nodes / included indexes work as well (using that info instead of or in addition to rowid/primary key as the last value there)


It's actually a List<Tuple<date, number, rowid>>> in sorted order, and queries are more akin to binary search (they are not actually binary but use a wider fanout depending on many factors)


Yeah it might be closer to what's actually happening but it doesn't make it obvious why something doesn't work. The map model doesn't even cover non-unique indices. Or different type of indexes.


It's _not_ just a list in sorted order; if it were, you could not insert efficiently into it. But the tuple is the right mental model, indeed.


That is a helpful way of thinking about it. Thanks for sharing!




Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: