[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)