3 ms·

> 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

by twic 8y ago

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

Dylan16807 8y ago
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.
ben509 8y ago
> 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.)

by twic 8y ago

Dylan16807 8y ago

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.

ben509 8y ago

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