4 ms·
Newbie database question: I'm surprised the database cares at all about field length for indexing purposes, because I'd assume for indexing purposes it would h
by shadowgovt 6y ago
Newbie database question:
I'm surprised the database cares at all about field length for indexing purposes, because I'd assume for indexing purposes it would hash the field and be done with it; a hash is a great tool for doing quick equality-comparisons.
Is this not sufficient because the index also needs to support sorting, so the original values matter to high resolution?
- throwaway81523 6y agoHash indexing is sometimes used, but B-trees are more common so you can select with ORDER BY and also because you can insert additional records as many times as you want, by splitting nodes now and then, but never having to rehash the whole index.
- ericyan 6y agoHash index is only useful for exact matches, a full table scan would be required for any other kinds of queries. That is why most database engines have settled with B+ tree. Regardless the type of index, field length still matters if you care about performance. Smaller fields and smaller indices means you can fits more things (the working set) in RAM and less I/O when you have to hit disks.
- masklinn 6y agoDatabases 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).
- zeroimpl 6y agoHash tables perform poorly when they need to be resized periodically as the table grows (as everything needs to get rehashed). Using a tree structure instead ensures consistent performance.