3 ms·

I thought a lot of b(+)tree advantage was in bigger-than-RAM something or other for large databases and these benchmarks seem relatively small in comparison

foota 2y ago
B-Trees are good for in memory data too because they have fairly good cache behavior.
robertclaus 2y ago
Ya, I would be curious to see how this performs on out-of-cache data on an SSD and actual hard drive. On the other hand, the findings are definitely still relevant since RAM has gotten fairly cheap and most applications probably fit in it just fine. Regarding databases - Btrees also have a natural sort order, which hash tables don't. This means a btree as your main data structure helps with sort, range, or list operations in a way a hash tables can't. That being said, even traditional databases obviously still use hash tables extensively (ex. Hash joins).
- scotty79 2y ago
  In Rust thanks to it you can have BTreeSet of BTreeSet-s.
  - deleted 2y ago
    [deleted]
  - scotty79 2y ago
    I think my comment was way too short. What I meant was that I needed a set type in Rust. At first I tried to use HashSet but I needed it's elements to also be sets. I couldn't because HashSet doesn't itself have a natural Hash. I'd need to implement it myself. However while using BTreeSet the requirement on the elements is that they have natural ordering (have Ord trait) but the BTreeSet itself also implements Ord so I could have a BTreeSet of BTreeSets without implementing anything additionally. Thanks to the fact that BTrees have natural ordering. So I used BTreeSet instead,
xxs 2y ago
b-trees are just 'better' binary trees as they have lower amounts of indirections (nodes)
crest 2y ago
As long as your puny little working set (2^16 small keys) fits into L2 cache and get is perfectly covered by the L1 dTLB you won't see the cost of touching random pages in a big hash table larger than the last level TLB coverage and on chip caches. There won't be any TLB stalls waiting for the page walkers and you won't miss the lost spacial locality in the key-space preserved by B(+)trees if everything is in L2 cache. At the very least it proves that hash tables can be a good fit for point queries of datasets too large for linear searching or sorting + binary searches, but not yet large enough to exhaust CPU cache capacity.
marginalia_nu 2y ago
You can line them up with disk blocks, or with CPU cache lines, the effect is relatively similar.

foota 2y ago

B-Trees are good for in memory data too because they have fairly good cache behavior.

robertclaus 2y ago

Ya, I would be curious to see how this performs on out-of-cache data on an SSD and actual hard drive. On the other hand, the findings are definitely still relevant since RAM has gotten fairly cheap and most applications probably fit in it just fine. Regarding databases - Btrees also have a natural sort order, which hash tables don't. This means a btree as your main data structure helps with sort, range, or list operations in a way a hash tables can't. That being said, even traditional databases obviously still use hash tables extensively (ex. Hash joins).

scotty79 2y ago
In Rust thanks to it you can have BTreeSet of BTreeSet-s.
- deleted 2y ago
  [deleted]
- scotty79 2y ago
  I think my comment was way too short. What I meant was that I needed a set type in Rust. At first I tried to use HashSet but I needed it's elements to also be sets. I couldn't because HashSet doesn't itself have a natural Hash. I'd need to implement it myself. However while using BTreeSet the requirement on the elements is that they have natural ordering (have Ord trait) but the BTreeSet itself also implements Ord so I could have a BTreeSet of BTreeSets without implementing anything additionally. Thanks to the fact that BTrees have natural ordering. So I used BTreeSet instead,

xxs 2y ago

b-trees are just 'better' binary trees as they have lower amounts of indirections (nodes)

crest 2y ago

As long as your puny little working set (2^16 small keys) fits into L2 cache and get is perfectly covered by the L1 dTLB you won't see the cost of touching random pages in a big hash table larger than the last level TLB coverage and on chip caches. There won't be any TLB stalls waiting for the page walkers and you won't miss the lost spacial locality in the key-space preserved by B(+)trees if everything is in L2 cache. At the very least it proves that hash tables can be a good fit for point queries of datasets too large for linear searching or sorting + binary searches, but not yet large enough to exhaust CPU cache capacity.

marginalia_nu 2y ago

You can line them up with disk blocks, or with CPU cache lines, the effect is relatively similar.