3 ms·
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 bran
by 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 agothanks, this seems in agreement with what i thought, except that i hadn't thought about the upsert advantage