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-... 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
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.
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-... 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