3 ms·
Does anyone here know if there’s a data structure more ideal (i.e. lower-overhead) than a B+-tree for holding onto large amounts of on-disk data, if you can con
by derefr 7y ago
Does anyone here know if there’s a data structure more ideal (i.e. lower-overhead) than a B+-tree for holding onto large amounts of on-disk data, if you can constrain the operations you’re going to do? Personally, in my workload, I know I’m never going to delete from the tree, only insert and query. Does this “get me” anything?
For another consideration: B+-trees (or trees generally) aren’t necessarily the best when the workload is mostly appends to the end of the keyspace. Is there an on-disk data structure that is tuned for mostly-append, rarely-insert workloads? Or how about for insert workloads, where each insert is actually a batch of inserts of a large contiguous range of sorted keys? (I’ve observed that this workload makes LevelDB fall over, so LSM trees aren’t it.)
- kyralis 7y agoI've personally used a B+Tree variant in this case with special-cased insert rules. Rather than splitting nodes when they're full, if they're filled due to appending at the right-hand-side we simply start the next leaf (or next interior + leaf pair) during insert. So, for pure in-order insertions, we end up with a maximally efficient tree with no splits needed; the rest of the logic still works if you then go back and need to update or insert into the middle of the tree at a later date. I'm sure I'm not the only one with that particular implementation, but I'm not aware of any named algorithm/variant for it.