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 geophile on Monday December 09, 2019 @11:28PM (#21749581)
No. This discussion is about algorithmic complexity, typically counting comparisons. And of course, it ignores constants. If we're counting page accesses, we care very much about the constants.

And furthermore, a "multi-level hash table" is a tree, except an unordered one. What a useless beast!

[ Parent | on HN ]
Re:Why databases use ordered indexes but programming uses ha... by AstralStorm on Tuesday December 10, 2019 @06:53AM (#21751632)
Yes, mostly. There are better structures with these characteristics like a skiplist, multihashed table (typically double hashed) or extensible hashing.
[ Parent | on HN ]
Re:Why databases use ordered indexes but programming uses ha... by misterman0 on Tuesday December 10, 2019 @02:51AM (#21750531)
>> What a useless beast!

Mostly but not entirely. There are cases where you need a tree but you don't care about order, e.g. when order depends on a state that is unknown at time of writing or when all you want to encode are relationships.

[ Parent | on HN ]
Re:Why databases use ordered indexes but programming uses ha... by andrewflnr on Tuesday December 10, 2019 @11:16PM (#21759534)
Also, JSON and its ilk.
[ Parent | on HN ]