3 ms·
If you know the answer, and you are pretty persistent in nudging it in the right direction, it will eventually give you the answer you expect. > I have a sorte
by marginalia_nu 4y ago
If you know the answer, and you are pretty persistent in nudging it in the right direction, it will eventually give you the answer you expect.
> I have a sorted list of integers and a B-Tree that is much larger than the list of integers. I want to find which integers exist in the b-tree as quickly as possible.
> This is a naive solution. Can't I re-use the knowledge gained from finding one item in the B-Tree to reduce the computation for finding or excluding the next?
> This is inefficient because it traverses the entire B-tree. The B-tree is very large, and the tree itself excluding leaf nodes is longer than the list. The leaf nodes are relatively large, but smaller than the list of numbers.
> What if I look at the first item in the list, and then find the corresponding leaf in the b-tree and compare it with items in the list until they no longer belong in that node, and then repeat the process by finding the next leaf node and comparing items in the list.
> Doesn't a b-tree have more than 2 nodes?
[It seems to have real trouble distinguishing between b-trees and binary trees.]
> What if I look at the first item in the list, and then find the corresponding leaf in the b-tree and compare it with items in the list until they no longer belong in that node, and then repeat the process by finding the next leaf node and comparing items in the list.
> What if the next leaf node is found by traversing from the root node looking for the next item in the list, rather than brute force searching the entire tree? The tree is much larger than the list and visiting each leaf node is slow.
> Are you sure the time complexity isn't linear?
[ n.b. this isn't actually true, but I wanted to see if it would agree ]
> The leaf nodes in a b-tree are pretty large compared to other tree types. Is the height of the b-tree really expected to be a significant factor on realistic hardware? Assume leaf node sizes of 512 and a tree no larger than 128 Gb.