News for hackers. Stuff that matters.

A comment on Why databases use ordered indexes but programming uses hash tables. Parent comment

Re:Why databases use ordered indexes but programming uses ha... by loeg on Tuesday December 10, 2019 @12:42AM (#21749939)
Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point queries are sufficient); binary trees have terrible cache locality.
[ Parent | on HN ]
Re:Why databases use ordered indexes but programming uses ha... by kccqzy on Tuesday December 10, 2019 @02:53AM (#21750539)
Cache locality issues can be fixed by using a good allocator (or a good compacting GC).
[ Parent | on HN ]
Re:Why databases use ordered indexes but programming uses ha... by AstralStorm on Tuesday December 10, 2019 @07:17AM (#21751751)
How can an allocator optimize the layout of a dynamically sized structure that's being changed without compacting?

Now, compacting is an O(n) memory move plus additional calculation to figure out optimal-ish layout.

(Can be amortized, but it's same as amortizing hash table resizing. Optimal layout cannot be decided without profiling, and that's expensive.)

[ Parent | on HN ]