Discussion
BtrFS is called such since it builds heavily upon BTrees. So what are BTrees, & how well would they suite our string-centric CPU?
Its a harddrive/cache friendly datastructure implementing a large ordered dictionary, thus speeding up looking up values by their keys or key-range. Which stays fast regardless of how you throw data into it.
Each page of a BTree stores an ordered sequence of keys & the subtrees between them. The final row (or all nodes) store the corresponding values.
1/3?
@alcinnz
I've head that there's an even better structure called, iirc, B+trees? Bcachefs uses them.
(They're not in ZFS or btrfs because they were invented more recently than those)
@kirtai Yeah, they're a variant which stores all values in the leaves & connects said leaves into a linkedlist. This makes range queries faster!
@alcinnz
I've head that there's an even better structure called, iirc, B+trees? Bcachefs uses them.
(They're not in ZFS or btrfs because they were invented more recently than those)
To lookup a value we scan a "root" page to find between which of its keys ours lie, to determine which subtree it should traverse into. Until it reaches a leaf, at which point it can return the corresponding value.
Inserting a key-value pair works similarly, until the leaf page we've appended it to overflows. In which case we split the leaf in half & insert the split point into its parent page. Repeat if that overflows too until its no longer an issue or we've got a new root.
2/3!
As for deletion, we lookup which page we should insert it into. If that page drops below half full, merge it with a neighbouring half-full page removing a key from the parent. Repeat for parent pages as necessary.
Regarding my hypothetical string-centric CPU... I'd reformat the keys as a program for our Parsing Unit (aided by our Arithmetic for the final comparison) to locate the 1st key in an array that's greater than our target. Our Output Unit can handle the recursion.
3/3 Fin for today!
Install bonfire.cafe
Get the full app experience
