News for hackers. Stuff that matters.
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.)

There are no comments on this comment yet.