4 ms·
Databases use btree indices for two reasons: 1. They provide much better locality and updatability, because databases would historically get the data from extr
by masklinn 6y ago
Databases use btree indices for two reasons:
1. They provide much better locality and updatability, because databases would historically get the data from extremely slow IO (spinning rust) btrees are a great fit, they're also extremely predictable (search, insert, and delete work in O(log n)).
2. hash indices only support exact matches, btrees support prefix and range matching, and they are ordered, so when all the stars align you don't even need to touch the data pages, you can serve an entire query by just reading the index.
Most databases allow opt-in hash indexes (and even other more complicated forms of indexes), but these are either much less flexible (hash) or much more expensive (gist/gin). The btree remains an excellent default.
- TazeTSchnitzel 6y agoPrefixes are a neat trick. One nice consequence is that an index for the column pair (a, b) is also an index for (a).