4 ms·

The Hitchhiker Tree [1] addresses the write amplification at the cost of making lookups and scans slightly more expensive, by keeping a small array of "pending

by ruuda 3y ago

The Hitchhiker Tree [1] addresses the write amplification at the cost of making lookups and scans slightly more expensive, by keeping a small array of "pending writes" in every non-leaf node. The entire thing is still immutable, but instead of writing a new leaf node + path from root to that leaf, in the majority of cases we only write a new root. When there is no space left in the array, all the pending values get pushed one level down at the same time, so the write amplification is amortized. [1]: https://www.youtube.com/watch?v=jdn617M3-P4 https://www.youtube.com/watch?v=jdn617M3-P4

ww520 3y ago
I believe the Bw-tree does the same thing, caching new updates in the intermediate branch nodes and only pushing the updates in batch down to the lower layers when running out of room at the branch node. These are the newer wave of algorithms to address the write amplification.
senderista 3y ago
This idea dates to at least 1996: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=5353ed87f7ec15c32d66f81a0ad9ba2f695f0855 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...
- kragen 3y ago
  can you explain the similarities and differences between arge's 'buffer tree' and the fractal tree and hitchhiker tree? my tentative understanding is that arge's work, applied to an ordinary search tree, yields something very similar to the fractal tree, except that it will opportunistically flush buffers before they are full if the child nodes they route to must be brought in from disk anyway to answer a read query. but arge is more concerned with applying the technique to hairier data structures like segment trees and binary decision diagrams. and the hitchhiker tree seems to be precisely a copy-on-write fractal tree, no more and no less. but possibly i am misunderstanding something? there's a clear citation path, so maybe i can untangle this: greenberg describes the hitchhiker tree as 'synthesizing fractal trees and functional data structures', kuszmaul's 02011 slide deck https://www.percona.com/blog/wp-content/uploads/2011/11/how-fractal-trees-work.pdf https://www.percona.com/blog/wp-content/uploads/2011/11/how-... cites brodal and fagerberg (02003, though he says 02002) and buchsbaum, goldwasser, venkatasubramanian, and westbrook (02000, though he says 02006), both of whom cite arge's 01996 paper
  - ww520 3y ago
    I think the main difference between Buffer Tree (Arge, Brodal and Fagerberg) and the more modern B-epsilon/Fractal/Hitchhiker Trees is what's stored in the branch buffer. Buffer Tree stores the data in the buffer. The newer Trees store the commands on data in the buffer, i.e. storing [insert(x), delete(y), update(a: 1), upsert(b: 2)] instead of [x, y, 1, 2]. The command+value are the data being migrated to the lower layers. The older papers just allude to "data" and show the asymptotic analysis. Having commands is better because you can preserve the order of operations as multiple operations against the same record coming down the layers. Also it can short-circuit query at higher nodes, e.g. it's deleted. Upsert is much faster with a single upsert command added to the root node's buffer than the typical query-modify-write cycle.
    - kragen 3y ago
      thanks, this seems in agreement with what i thought, except that i hadn't thought about the upsert advantage
- ww520 3y ago
  Here're what I found on the idea of adding buffers to branch nodes. L. Arge described the Buffer Tree idea in 1995 with (a,b)-Tree for other data structures. Brodal and Fagerberg formalized it for B+Tree in 2003. There's also the more modern Bε-Tree, the B-epsilon Tree, with similar idea, used in the BetrFS file system and various DBs. Tokutek built TokuDB using a similar idea and called it Fractal Tree (which was derived from Bε-Tree). Hitchhicker Tree is the append-only version of Fractal Tree, similar to the append-only B+Tree. * L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 334–345, Springer Verlag, Berlin. 1995. https://link.springer.com/chapter/10.1007/3-540-60220-8_74 https://link.springer.com/chapter/10.1007/3-540-60220-8_74 * G. S. Brodal, R. Fagerberg. Lower Bounds for External Memory Dictionaries. 2003. https://cs.au.dk/~gerth/papers/soda03.pdf https://cs.au.dk/~gerth/papers/soda03.pdf * Bε-Tree, https://www.betrfs.org/ https://www.betrfs.org/, https://www.youtube.com/watch?v=fBt5NuNsoII https://www.youtube.com/watch?v=fBt5NuNsoII. An Introduction to Bε-trees and Write-Optimization, http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf, https://www.youtube.com/watch?v=v_g4eZeWAng&t=15s https://www.youtube.com/watch?v=v_g4eZeWAng&t=15s * Tokutek. How Fractal Trees Work. 2011. https://www.percona.com/blog/wp-content/uploads/2011/11/how-fractal-trees-work.pdf https://www.percona.com/blog/wp-content/uploads/2011/11/how-... * Hitchhiker Tree. 2016. https://github.com/datacrypt-project/hitchhiker-tree https://github.com/datacrypt-project/hitchhiker-tree

by ruuda 3y ago

ww520 3y ago

I believe the Bw-tree does the same thing, caching new updates in the intermediate branch nodes and only pushing the updates in batch down to the lower layers when running out of room at the branch node. These are the newer wave of algorithms to address the write amplification.

senderista 3y ago

This idea dates to at least 1996: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=5353ed87f7ec15c32d66f81a0ad9ba2f695f0855 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

kragen 3y ago
can you explain the similarities and differences between arge's 'buffer tree' and the fractal tree and hitchhiker tree? my tentative understanding is that arge's work, applied to an ordinary search tree, yields something very similar to the fractal tree, except that it will opportunistically flush buffers before they are full if the child nodes they route to must be brought in from disk anyway to answer a read query. but arge is more concerned with applying the technique to hairier data structures like segment trees and binary decision diagrams. and the hitchhiker tree seems to be precisely a copy-on-write fractal tree, no more and no less. but possibly i am misunderstanding something? there's a clear citation path, so maybe i can untangle this: greenberg describes the hitchhiker tree as 'synthesizing fractal trees and functional data structures', kuszmaul's 02011 slide deck https://www.percona.com/blog/wp-content/uploads/2011/11/how-fractal-trees-work.pdf https://www.percona.com/blog/wp-content/uploads/2011/11/how-... cites brodal and fagerberg (02003, though he says 02002) and buchsbaum, goldwasser, venkatasubramanian, and westbrook (02000, though he says 02006), both of whom cite arge's 01996 paper
- ww520 3y ago
  I think the main difference between Buffer Tree (Arge, Brodal and Fagerberg) and the more modern B-epsilon/Fractal/Hitchhiker Trees is what's stored in the branch buffer. Buffer Tree stores the data in the buffer. The newer Trees store the commands on data in the buffer, i.e. storing [insert(x), delete(y), update(a: 1), upsert(b: 2)] instead of [x, y, 1, 2]. The command+value are the data being migrated to the lower layers. The older papers just allude to "data" and show the asymptotic analysis. Having commands is better because you can preserve the order of operations as multiple operations against the same record coming down the layers. Also it can short-circuit query at higher nodes, e.g. it's deleted. Upsert is much faster with a single upsert command added to the root node's buffer than the typical query-modify-write cycle.
  - kragen 3y ago
    thanks, this seems in agreement with what i thought, except that i hadn't thought about the upsert advantage
ww520 3y ago
Here're what I found on the idea of adding buffers to branch nodes. L. Arge described the Buffer Tree idea in 1995 with (a,b)-Tree for other data structures. Brodal and Fagerberg formalized it for B+Tree in 2003. There's also the more modern Bε-Tree, the B-epsilon Tree, with similar idea, used in the BetrFS file system and various DBs. Tokutek built TokuDB using a similar idea and called it Fractal Tree (which was derived from Bε-Tree). Hitchhicker Tree is the append-only version of Fractal Tree, similar to the append-only B+Tree. * L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In Proc. 4th Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 334–345, Springer Verlag, Berlin. 1995. https://link.springer.com/chapter/10.1007/3-540-60220-8_74 https://link.springer.com/chapter/10.1007/3-540-60220-8_74 * G. S. Brodal, R. Fagerberg. Lower Bounds for External Memory Dictionaries. 2003. https://cs.au.dk/~gerth/papers/soda03.pdf https://cs.au.dk/~gerth/papers/soda03.pdf * Bε-Tree, https://www.betrfs.org/ https://www.betrfs.org/, https://www.youtube.com/watch?v=fBt5NuNsoII https://www.youtube.com/watch?v=fBt5NuNsoII. An Introduction to Bε-trees and Write-Optimization, http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf, https://www.youtube.com/watch?v=v_g4eZeWAng&t=15s https://www.youtube.com/watch?v=v_g4eZeWAng&t=15s * Tokutek. How Fractal Trees Work. 2011. https://www.percona.com/blog/wp-content/uploads/2011/11/how-fractal-trees-work.pdf https://www.percona.com/blog/wp-content/uploads/2011/11/how-... * Hitchhiker Tree. 2016. https://github.com/datacrypt-project/hitchhiker-tree https://github.com/datacrypt-project/hitchhiker-tree