1. 29

  2. 3

    There are a lot of fun twists on this idea that are floating around. A few databases based on Bw-Trees (sled, OpenBw-Tree) have iterators just cache the last tree node locally to avoid any index traversal while zipping through the tree sequentially.

    The actual benefit is workload-dependent for most types of index-lookup caching. 5% perf hit on a miss is actually a fairly significant cost for this kind of structure, and if access patterns tend to traverse different children from the root onward most of the time, it will be a net negative. Non-test datasets tend to dwarf those used by engineers while tuning their systems most of the time, and the larger the dataset, the worse the hit for random-access workloads. The question that interests me is how to dynamically detect access patterns that would justify certain types of lookup optimizations, and do them in a way that still plays nicely with memory reclamation and correctness requirements for the overall system.

    1. 2

      I’m actually implementing a b-tree storage manager right now. One of the things I realized only after writing the search and mutation code, and moving on to cursors, is that it makes a lot of sense to put the former inside the latter — that is, make search/insert/delete be operations on cursors.

      Partly this is because my cursor class stores its path: a list of (page#, key index) pairs leading from the root to the current position.

      • The “seek” operation on a cursor is basically the same code as looking up a key in the b-tree, it just doesn’t directly return the value. And the benefit is that it remembers the path. The next seek can use this path as an optimization, which is what’s discussed in this post.
      • Insertion and deletion are recursive, since you have to first find the leaf node, and then walk back up fixing up parents if any node moves or splits/merges. The cursor’s path lets you do this easily without actually recursing; instead you just iteratively walk back up the path.

      So in my code as of yesterday, the BTree methods find, insert and remove are just trivial wrappers around the corresponding Cursor methods. The BTree object keeps a Cursor instance that it delegates these to. Or of course the application code can create and call it’s own Cursor instances.

      1. 2

        Interesting. Ideas:

        • Would it make sense to let the user keep track of paths. Might be useful for stuff like pagination, or bulk insertion.
        • Could a DB keep a LRU cache of last used paths, and on each lookup find the the path corresponding for a key equal, or a use a common prefix of paths for the fist lower and first higher element in the cache? Do DBs do something like that already?
        1. 2

          In a lot of ways this is like having the user keep a cursor object around, since a cursor remembers its path (see my other comment.) The difficulty would be for the library keep a cursor’s state up to date when modifications are made to the tree not using that cursor.

          1. 1

            It’s like a cursor, but it’s still only a hint. The DB is free to ignore it as soon as it determines that it’s wrong.