[HN Gopher] How does a B-tree make queries fast? ___________________________________________________________________ How does a B-tree make queries fast? Author : jaycox2931 Score : 30 points Date : 2023-12-23 21:33 UTC (1 hours ago) (HTM) web link (blog.allegro.tech) (TXT) w3m dump (blog.allegro.tech) | marginalia_nu wrote: | Another neat part is that, for intersecting different B-trees, | you can use an algorithm like this to get very efficient | algorithm: https://nlp.stanford.edu/IR- | book/html/htmledition/faster-pos... | | (Here discussed in terms of skip lists, but they are similar | enough that the distinction doesn't matter) | o11c wrote: | Note that the real primitive is "find nearest [with hint]", | which has to be the #1 thing I miss in Python. | | For B-trees it's only going to be a significant win if the | chance of intersection is small, less than about | `1/(nodes_per_block)`. For binary trees it's a much bigger win | since that becomes 1/2 and binary trees are horrible on cache. | | Hmm, can you efficiently intersect an arbitrary number of | B-trees using the same idea as a heap-merge, but with a max | heap instead of a min heap? You'd still have to iterate over | all on a match, but as long as 2 input trees don't have an | intersection, you don't have to look at the others at all ... | or does that become equivalent to just doing them in series? | daveevad wrote: | It's not that deep. ___________________________________________________________________ (page generated 2023-12-23 23:00 UTC)