3 ms·

Isn't a B-tree more suited for this purpose than a hash table?

epistasis 14y ago
I don't think so, but I'm all ears to suggestions. I was playing around with string search where the haystack is large, fixed, and searched for small needles whose total volume is thousands of times larger than the haystack. My goal is to optimize the number of lookups per second on approximately ~2.5 billion keys, and each value is 4 bytes long; and for this particular application I can lookup the keys in each hash bucket super quickly once I know the values. The benefits of B-trees over hash tables don't matter in this application, as I don't care about adjacent keys after lookup, and the input order of my keys is not going to be sorted in any way so once I find a leaf it's not going to help me with subsequent lookups. In this setting it seems that any B-tree access is going to require traversing several new nodes in addition to the first node, and those internal nodes are extremely likely to be both cache-cold and TLB cold. Whereas with a hash table I only have a single cold memory lookup to check the hash bucket, then a single cold memory lookup to validate the key at the bucket matches; this cold memory lookup for the validation is also likely to warm the cache for the subsequent matching work, and this small amount of subsequent matching work would likely be required by a B-Tree as well. Any thoughts?
- andreasvc 14y ago
  I see. Note that the amount of lookups for the hash table only holds if there is no collision, but that may be a fair assumption. Given that the data are strings, a specialized datastructure such as a Trie or suffix array might work well, especially if it is possible to exploit redundancy in the data (i.e., repeated substrings). There are specialized datastructures used in full-text search which will probably be useful. In any case dealing with this amount of data might mean that using an off-the-shelf database might be a good idea.

I don't think so, but I'm all ears to suggestions. I was playing around with string search where the haystack is large, fixed, and searched for small needles whose total volume is thousands of times larger than the haystack. My goal is to optimize the number of lookups per second on approximately ~2.5 billion keys, and each value is 4 bytes long; and for this particular application I can lookup the keys in each hash bucket super quickly once I know the values. The benefits of B-trees over hash tables don't matter in this application, as I don't care about adjacent keys after lookup, and the input order of my keys is not going to be sorted in any way so once I find a leaf it's not going to help me with subsequent lookups. In this setting it seems that any B-tree access is going to require traversing several new nodes in addition to the first node, and those internal nodes are extremely likely to be both cache-cold and TLB cold. Whereas with a hash table I only have a single cold memory lookup to check the hash bucket, then a single cold memory lookup to validate the key at the bucket matches; this cold memory lookup for the validation is also likely to warm the cache for the subsequent matching work, and this small amount of subsequent matching work would likely be required by a B-Tree as well. Any thoughts?

andreasvc 14y ago
I see. Note that the amount of lookups for the hash table only holds if there is no collision, but that may be a fair assumption. Given that the data are strings, a specialized datastructure such as a Trie or suffix array might work well, especially if it is possible to exploit redundancy in the data (i.e., repeated substrings). There are specialized datastructures used in full-text search which will probably be useful. In any case dealing with this amount of data might mean that using an off-the-shelf database might be a good idea.