3 ms·

B+Trees minimize the maximum depth of the lookup. All the values have exactly the same cost. In all honesty, I don't care about the lookup cost of the values I

B+Trees minimize the maximum depth of the lookup. All the values have exactly the same cost. In all honesty, I don't care about the lookup cost of the values I never need.

bob1029 5y ago
Sounds like you are looking for a Splay Tree implementation. Their dynamic optimality properties ensure your most popular data lives right at the root.
- toolslive 5y ago
  For example. In essence any tree that allows you to "rotate" based on some statistics about subtree popularity. This becomes more and more interesting in combination with copy-on-write strategies because there you have to rewrite the top of the tree anyway. So why not aggregate some statistics while you're at it.
  - jlokier 5y ago
    The "hot items" optimisation you're thinking of have less of an effect on trees with wide fanout, such as B-trees with a substantial block size. This is because the ratio of number of "hot" items you can store at a reduced depth to total number of item is a much smaller ratio with a high fanout tree than a low fanout tree; and at the same time, the depths are lower with a high fanout tree, reducing the benefit of reduced depth anyway. In other words, you can only give the benefit to a smaller number of hot items, and the benefit you can give is smaller. On top of that, the added complications of rotations and statistics mean fewer items can be stored in interior nodes (which I'd call index nodes) for a given node size. This reduces the fanout and increases the full depth. And the rotations and access statistics cause more writing. There are tradeoffs and perhaps it is worth it for some tree parameters. Perhaps for exceptionally large trees with particular access patterns. It would be interesting to see how it's implemented. But generally for a high-fanout B-tree, you might as well just store frequently accessed items in a separate small tree as a cache, and keep that cached in memory.
    - toolslive 5y ago
      You're absolutely right. However a cow strategy forces you to rewrite parts of the tree _anyway_ (typically the path from the node you're updating to the root). So you might as well rotate an out of balance node in that path. The rewriting also causes you to shy away from high fanouts because of the overhead.
      - jlokier 5y ago
        Well, I would definitely be interested to see the paper where that B-tree rotation is described along with measurements! There are many effective B-tree modifications; maybe that's one of them. At least with storage B-trees, I haven't seen a paper describing anything like that yet. One of the "rules of thumb" of optimising high-fanout B-trees larger than memory is to generally put values in the leaves, because the benefit of being able to keep more pointers cached in memory in compact internal nodes to help locate values in fewer I/O steps outweighs the benefit of having an arbitrary and small subset of larger values in the internal nodes. But if you have particularly well-chosen larger values in the internal nodes, and a low-entropy access pattern, perhaps the rule of thumb doesn't apply then. There are quite a few B-tree modifications where separate small trees or logs or both are maintained to improve performance, but these are generally to optimise writes, which can be sorted and distributed in batches to reduce random access block I/O, rather than to optimise frequently accessed reads by acting as an on-storage persistent cache. On fanout: High fanout is generally used with storage devices, because low fanout always increases the overhead. For example on NVMe SSDs I've used, reading or writing any block smaller than 4096 bytes takes the same time as 4096 bytes. On HDDs the equivalent number is much larger due to seek time. So lowering fanout below 4096 bytes per block would just increase the number of block I/Os per tree operation. without reducing the time per I/O. On COW: You're right about the rewriting, although it's worth knowing that times have changed: On NVMe you have durable write atomicity guarantees so you don't need to COW as much to have the same storage guarantees. Inside the NVMe of course it may be doing COW on hidden page remappings to provide this atomicity, or it may use other techniques (e.g. a supercapacitor to ensure writes always complete) but from the outside you can simply overwrite blocks or parts of blocks in place. This adds quite a saving to safe tree updates, and it also reduces padding required in write-ahead logs at durable commit points, including the in-block logs used in several B-tree optimisations (e.g. see bcache on Linux). Even with COW, it isn't always necessary to update the path to the root by rewriting parent blocks in general. To avoid a parent block write, sometimes it's faster to log an update to the parent's pointer entry, either in an actual logical log somewhere, or using a separate logical to physical page mapping table, or by using pointer-to-log entries that are resolved at read time. If it's an in-memory B-tree, a COW strategy doesn't need to rewrite parent blocks at all. It can update the pointers in place directly with atomic pointer updates, although some implementations prefer a logical-to-physical page mapping table instead and to atomically update the table.

B+Trees minimize the maximum depth of the lookup. All the values have exactly the same cost. In all honesty, I don't care about the lookup cost of the values I never need.

bob1029 5y ago

Sounds like you are looking for a Splay Tree implementation. Their dynamic optimality properties ensure your most popular data lives right at the root.

toolslive 5y ago
For example. In essence any tree that allows you to "rotate" based on some statistics about subtree popularity. This becomes more and more interesting in combination with copy-on-write strategies because there you have to rewrite the top of the tree anyway. So why not aggregate some statistics while you're at it.
- jlokier 5y ago
  The "hot items" optimisation you're thinking of have less of an effect on trees with wide fanout, such as B-trees with a substantial block size. This is because the ratio of number of "hot" items you can store at a reduced depth to total number of item is a much smaller ratio with a high fanout tree than a low fanout tree; and at the same time, the depths are lower with a high fanout tree, reducing the benefit of reduced depth anyway. In other words, you can only give the benefit to a smaller number of hot items, and the benefit you can give is smaller. On top of that, the added complications of rotations and statistics mean fewer items can be stored in interior nodes (which I'd call index nodes) for a given node size. This reduces the fanout and increases the full depth. And the rotations and access statistics cause more writing. There are tradeoffs and perhaps it is worth it for some tree parameters. Perhaps for exceptionally large trees with particular access patterns. It would be interesting to see how it's implemented. But generally for a high-fanout B-tree, you might as well just store frequently accessed items in a separate small tree as a cache, and keep that cached in memory.
  - toolslive 5y ago
    You're absolutely right. However a cow strategy forces you to rewrite parts of the tree _anyway_ (typically the path from the node you're updating to the root). So you might as well rotate an out of balance node in that path. The rewriting also causes you to shy away from high fanouts because of the overhead.
    - jlokier 5y ago
      Well, I would definitely be interested to see the paper where that B-tree rotation is described along with measurements! There are many effective B-tree modifications; maybe that's one of them. At least with storage B-trees, I haven't seen a paper describing anything like that yet. One of the "rules of thumb" of optimising high-fanout B-trees larger than memory is to generally put values in the leaves, because the benefit of being able to keep more pointers cached in memory in compact internal nodes to help locate values in fewer I/O steps outweighs the benefit of having an arbitrary and small subset of larger values in the internal nodes. But if you have particularly well-chosen larger values in the internal nodes, and a low-entropy access pattern, perhaps the rule of thumb doesn't apply then. There are quite a few B-tree modifications where separate small trees or logs or both are maintained to improve performance, but these are generally to optimise writes, which can be sorted and distributed in batches to reduce random access block I/O, rather than to optimise frequently accessed reads by acting as an on-storage persistent cache. On fanout: High fanout is generally used with storage devices, because low fanout always increases the overhead. For example on NVMe SSDs I've used, reading or writing any block smaller than 4096 bytes takes the same time as 4096 bytes. On HDDs the equivalent number is much larger due to seek time. So lowering fanout below 4096 bytes per block would just increase the number of block I/Os per tree operation. without reducing the time per I/O. On COW: You're right about the rewriting, although it's worth knowing that times have changed: On NVMe you have durable write atomicity guarantees so you don't need to COW as much to have the same storage guarantees. Inside the NVMe of course it may be doing COW on hidden page remappings to provide this atomicity, or it may use other techniques (e.g. a supercapacitor to ensure writes always complete) but from the outside you can simply overwrite blocks or parts of blocks in place. This adds quite a saving to safe tree updates, and it also reduces padding required in write-ahead logs at durable commit points, including the in-block logs used in several B-tree optimisations (e.g. see bcache on Linux). Even with COW, it isn't always necessary to update the path to the root by rewriting parent blocks in general. To avoid a parent block write, sometimes it's faster to log an update to the parent's pointer entry, either in an actual logical log somewhere, or using a separate logical to physical page mapping table, or by using pointer-to-log entries that are resolved at read time. If it's an in-memory B-tree, a COW strategy doesn't need to rewrite parent blocks at all. It can update the pointers in place directly with atomic pointer updates, although some implementations prefer a logical-to-physical page mapping table instead and to atomically update the table.