> 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 n

> 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.)