News for hackers. Stuff that matters.
Re:How many ways are there to sort GUIDs? by Dylan16807 on Monday April 29, 2019 @11:38PM (#19784960)
Sometimes all you need is a dictionary, where you take a key and access a value. Both hash tables and binary-searchable trees are valid ways to accomplish this, with different speed tradeoffs. Binary search works just fine for this even when the keys are completely meaningless and random.

Databases especially have tons of operations where rows have unique meaningless keys that are used to represent relationships. And at the same time a hash table would mean going offline for hours when it resizes, so they use a tree and apply binary search over it to access rows.

Re:How many ways are there to sort GUIDs? by twic on Tuesday April 30, 2019 @02:10AM (#19785517)
> Both hash tables and binary-searchable trees are valid ways to accomplish this, with different speed tradeoffs.

Isn't a hashtable faster than a binary tree for basically all purposes? The only reason to use a tree is if you want to keep the data in order, but the only reason to do that is if the data has a meaningful order!

Re:How many ways are there to sort GUIDs? by ben509 on Tuesday April 30, 2019 @12:27PM (#19789375)
> Isn't a hashtable faster than a binary tree for basically all purposes?

They're heavily used in query optimization because it's great to build a hash table no one else is using. It all comes down to resizing the underlying buckets.

If you're doubling each time, that cost amortizes across updates; hence the claim there's a constant cost per update.

But while resizing, you have a choice: make the index inaccessible while it's updating, or fuck it, we'll do it live.

To do it live, you need to implement a fallback strategy that tries both copies. If your new buckets fill up before the first one has transferred, okay, we'll set up a third, but now our job has become that much more disk intensive.

And that's the real problem: on a server, you already have all kinds of processes and jobs running. Extra processes that can chew up hard-to-predict amounts of disk and CPU are more potential causes of instability. Plus, all these jobs need to be recoverable in case of a crash, etc.

Tree structures, OTOH, give you very predictable performance because you're only dealing with log N points on a tree. (B-trees just let you use a very big base for that log.)

Re:How many ways are there to sort GUIDs? by Dylan16807 on Tuesday April 30, 2019 @02:51AM (#19785686)
A hash table doesn't always have the best constant factors, and often wastes more space.

Also when you're in a situation where you need GUIDs to guarantee unique keys, and also you use a GUID variant with timestamps, many access patterns will go sort of in order and be far faster on a tree than a hash table. Even though the GUID itself is meaningless.