3 ms·

How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. A B-tree of any branching fac

How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. A B-tree of any branching factor (not only 2) is equivalent to a binary tree. We can take any B-tree node n: n | ---------+----------- | | | | | | a b c d e f and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every node of the B-tree, like from a to f, it as if we are traversing the unbalanced tree (except for constant-time instruction and cache level efficiencies). What the unbalanced tree cannot do is binary search through a to f to find which one to descend into; it doesn't have those nodes in a neat array for that. That binary search makes B-tree more or less equivalent to a very balanced binary tree.

jvanderbot 2y ago
I don't think so? I think the b-tree is using the start/end sequence knowledge at each to do fewer node evaluations. That is, a b-tree is "shorter" so of course it'll take fewer node evaluations to reach the leaf. "b-tree is equivalent to balanced binary tree", and "unbalanced tree", don't make a ton of sense when ostensibly the article compares b-trees to balanced BST.
bunderbunder 2y ago
Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.
- sam0x17 2y ago
  yeah locality of reference is way better as you're traversing the array than as you follow links in the tree
- shpongled 2y ago
  Definitely depends on the branching factor! There are other encodings like Eytzinger that can provide further improves over "standard" binary search too [1]. [1] https://en.algorithmica.org/hpc/data-structures/binary-search/ https://en.algorithmica.org/hpc/data-structures/binary-searc...
- kazinator 2y ago
  Suppose the key comparisons are much more expensive than the array or pointer navigation. Like the article does: it says that it is about theory, and it is looking at number of comparisons as the performance measure. The fact that we can search a B-tree node that has, say, 256 children in 8 steps means that the node effectively contains the equivalent of a small balanced binary tree.
- kevin_thibedeau 2y ago
  It does. The break even point varies by platform but linear will win for sufficiently short arrays.
- torginus 2y ago
  I remember reading a blogpost about this, they compared binary search on integer keys with a highly-optimized unrolled SIMD linear search. The takeaway was that the break-even point was suprising small - just tens of elements, which is crazy considering a CPU can do like 2x 8-wide AVX2 integer comparisons in a single cycle. Modern CPUs are just that good at executing branchy code. But with B-trees we can have the best of both worlds - trees with a relatively high branch factor, like 16, that can still be tested in one go using SIMD. Another advantage is cache locality - which is one of the reasons B-trees are favored when implementing filesystems - much of the tree doesn't need to be fetched into memory while the parts that do are contiguous in memory.
sqeaky 2y ago
I think you might be missing the real performance characteristics of the hardware. The amount of comparisons might be the same, but comparisons are only a proxy for the expensive parts of lookups, the latency to tell RAM to provide data. If the whole tree is in CPU cache then likely the difference is noise, but if the tree is large enough to have some data in RAM then the cost to copy that into cache will be larger based not on the size, but on the amount of queries from the CPU to the RAM (unless the size it way out of proportion). RAM has latency that is generally an order of magnitude slower than CPU Cache and generally an order of magnitude slower than fast contemporary storage. There are many places you can find "Latency numbers every programmer needs to know" https://fullstackengineer.pro/blog/latency-numbers-programmer https://fullstackengineer.pro/blog/latency-numbers-programme... But this trend has held for about 30 years and seem fundamental to the economics of building hardware. CPUs will be fastest, and cache slower, and RAM slower still , and fast storage still slower etc. From your example, if it takes 100ns to get the node containing a~f then the whole of the B-Tree search for f might take 150ns (1 lookup from RAM + a few CPU intructions), but with the strictly binary tree it will need 6 lookups to RAM, and we can see that we can ignore the CPU time because it is so small. This could take 600ns (or 1300ns if each branch is a node with only pointers and the data needs to be dereferenced too). A smart cache prefetcher might guess that these were pointers and precache a and b once n was referenced, and might even cache things pointed to by loaded pointers but even in that highly optimistic scenario it could still take 300ns to load stuff. Consider filesystems on storage and how they have had this problem but worse for a long time. Tree structures with many pointers are faster than binary trees in proportion to latency between the thing processing the tree and the place the tree it stored. EDIT - And don't get me started on clever use of SIMD instruction. Imagine if node in a tree had binary layout matching an AVX register, then comparisons looking for the searched item could check a whole node in a single instruction! I am curious if there are any implementations that do this? EDIT 2 - It does exist and I am late to the show, people have been doing this for like 15 years: https://stackoverflow.com/questions/20616605/using-simd-avx-sse-for-tree-traversal https://stackoverflow.com/questions/20616605/using-simd-avx-...
- deleted 2y ago
  [deleted]
- 2y ago

jvanderbot 2y ago

I don't think so? I think the b-tree is using the start/end sequence knowledge at each to do fewer node evaluations. That is, a b-tree is "shorter" so of course it'll take fewer node evaluations to reach the leaf. "b-tree is equivalent to balanced binary tree", and "unbalanced tree", don't make a ton of sense when ostensibly the article compares b-trees to balanced BST.

bunderbunder 2y ago

Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.

sam0x17 2y ago
yeah locality of reference is way better as you're traversing the array than as you follow links in the tree
shpongled 2y ago
Definitely depends on the branching factor! There are other encodings like Eytzinger that can provide further improves over "standard" binary search too [1]. [1] https://en.algorithmica.org/hpc/data-structures/binary-search/ https://en.algorithmica.org/hpc/data-structures/binary-searc...
kazinator 2y ago
Suppose the key comparisons are much more expensive than the array or pointer navigation. Like the article does: it says that it is about theory, and it is looking at number of comparisons as the performance measure. The fact that we can search a B-tree node that has, say, 256 children in 8 steps means that the node effectively contains the equivalent of a small balanced binary tree.
kevin_thibedeau 2y ago
It does. The break even point varies by platform but linear will win for sufficiently short arrays.
torginus 2y ago
I remember reading a blogpost about this, they compared binary search on integer keys with a highly-optimized unrolled SIMD linear search. The takeaway was that the break-even point was suprising small - just tens of elements, which is crazy considering a CPU can do like 2x 8-wide AVX2 integer comparisons in a single cycle. Modern CPUs are just that good at executing branchy code. But with B-trees we can have the best of both worlds - trees with a relatively high branch factor, like 16, that can still be tested in one go using SIMD. Another advantage is cache locality - which is one of the reasons B-trees are favored when implementing filesystems - much of the tree doesn't need to be fetched into memory while the parts that do are contiguous in memory.

sqeaky 2y ago

I think you might be missing the real performance characteristics of the hardware. The amount of comparisons might be the same, but comparisons are only a proxy for the expensive parts of lookups, the latency to tell RAM to provide data. If the whole tree is in CPU cache then likely the difference is noise, but if the tree is large enough to have some data in RAM then the cost to copy that into cache will be larger based not on the size, but on the amount of queries from the CPU to the RAM (unless the size it way out of proportion). RAM has latency that is generally an order of magnitude slower than CPU Cache and generally an order of magnitude slower than fast contemporary storage. There are many places you can find "Latency numbers every programmer needs to know" https://fullstackengineer.pro/blog/latency-numbers-programmer https://fullstackengineer.pro/blog/latency-numbers-programme... But this trend has held for about 30 years and seem fundamental to the economics of building hardware. CPUs will be fastest, and cache slower, and RAM slower still , and fast storage still slower etc. From your example, if it takes 100ns to get the node containing a~f then the whole of the B-Tree search for f might take 150ns (1 lookup from RAM + a few CPU intructions), but with the strictly binary tree it will need 6 lookups to RAM, and we can see that we can ignore the CPU time because it is so small. This could take 600ns (or 1300ns if each branch is a node with only pointers and the data needs to be dereferenced too). A smart cache prefetcher might guess that these were pointers and precache a and b once n was referenced, and might even cache things pointed to by loaded pointers but even in that highly optimistic scenario it could still take 300ns to load stuff. Consider filesystems on storage and how they have had this problem but worse for a long time. Tree structures with many pointers are faster than binary trees in proportion to latency between the thing processing the tree and the place the tree it stored. EDIT - And don't get me started on clever use of SIMD instruction. Imagine if node in a tree had binary layout matching an AVX register, then comparisons looking for the searched item could check a whole node in a single instruction! I am curious if there are any implementations that do this? EDIT 2 - It does exist and I am late to the show, people have been doing this for like 15 years: https://stackoverflow.com/questions/20616605/using-simd-avx-sse-for-tree-traversal https://stackoverflow.com/questions/20616605/using-simd-avx-...

deleted 2y ago
[deleted]
2y ago