Andrews’ Twigg and Byde patent application on #stratified-B-trees. Scumbags. #trees #patents
on 02015-09-09this "Stratified B-trees" paper presents “a fully-versioned B-tree with optimal space and the same lookup time as the [copy-on-write] B-tree”, and also supports fully-versioned updates in o(1) IOs in linear space, by merging sorted arrays of (key, version, value) tuples, followed by “density amplification” by de-merging the arrays if they are not dense enough (<⅓) in some of the versions. Nodes are immutable once written. May also be relevant to Cuerda. #algorithms #trees
on 02015-09-09