You follow along and build a toy B+-tree based sqlite clone in this (incomplete) tutorial.
Let’s Invent B(+)-Trees
31–40 of 72 posts
Re: Let’s Invent B(+)-Trees
#32Earlier quoted context omitted.
I guess I should have disambiguated my usage of "persistent". In this case it refers to a purely-functional data structure[1], not a data structure that is persisted to disk. Inserting an item into a persistent B-tree produces a new tree, while leaving the old one intact. Ideally, this is done with minimal copying; unchanged subtrees are just pointers to the same subtrees in the old tree. This is very similar to pers…
I see, the javascript world usually it call the "persistent" data structure as "immutable" data structure
Yeah that's the usual terminology in JS world. Persistence (the naming) comes out of algorithm theory, which IMO has pretty poor naming in general (dynamic programming and cache-oblivious also come to mind as unfortunate names). Not entirely sure why that is.
There's a few "levels" of persistence available, just as an aside. Immutability I think corresponds to the ~strongest level, but also means it can be hardest to achieve. One easier version allow only _querying_ old versions of the data structure for instance, no modifications except at the tip. Sometimes that's enough.
Re: Let’s Invent B(+)-Trees
#33I like this approach to describing B-trees! I recently taught B-trees for a data structures course and presented them using a similar method. Thought I'd leave the link in case it was useful: http://web.stanford.edu/class/cs166/lectures/05/Slides05.pdf
Re: Let’s Invent B(+)-Trees
#34Haha, his web directory layout cracked me up.
After reading, I thought to myself, "Hmm... I wonder what else he has written. I'll navigate upwards a level to https://shachaf.net/w "...
It returns a blank page with the letter "w". That actually made me laugh out loud.
"Ah, shucks. Let's go up again."
Returns a non-styled page that reads "Success!".
Re: Let’s Invent B(+)-Trees
#35This sounds exactly how the excellent Python Sorted Containers library works, and achieves "faster than C" performance in pure Python by effective use of the bisect module (which itself is written in C). http://www.grantjenks.com/docs/sortedcontainers/implementati... > The Sorted Containers internal implementation is based on a couple observations. The first is that Python’s list is fast, really fast. Lists have grea…
"Faster than C", by effective use of C? Maybe I'm missing something, but that seems to immediately be a contradiction.
Re: Let’s Invent B(+)-Trees
#36This is weirdly relevant. I just finished implementing a persistent B-tree library in Scheme.[1][2] I don't know why B-trees aren't used more as a purely-functional data structure. Once they get large enough, they don't move around much when changed; there is no rebalancing except on deletes, and even that only affects the direct path to the deleted node. [1] https://github.com/ar-nelson/schemepunk#b-trees [2] https:…
Log-structured-merge trees are that; they are not a functional data structure in memory, but on disk they are.
For those who don't know about this, here's how it works:
Construct a b-tree in memory ('level 0'). When it reaches a certain size, move it to disk (to L1, level 1) in a compact fashion (by building the tree from the leaf up. There is no need to keep spare space at any L1 node because it is a functional data structure, and won't be directly mutated. The L0-tree in RAM can now be scrapped, and built up from scratch with more insertions. Again, when it exceeds a threshold, the in-memory L0-tree and the on-disk L1 tree from earlier are merged to create a new L1 tree. This goes on until the L1 tree has grown beyond a level-1 threshold size (some k times the L0 size), at which point, the L1 tree is pushed into L2. And so on. L0 is in RAM, L1 and others are on disk.
Lookups are more expensive because multiple trees may have to be consulted, but with a judicious use of multiple cores and bloom filters, that cost can be recouped.
This avoidance of in-place mutations works esp. well with SSDs and other copy-on-write systems.
Re: Let’s Invent B(+)-Trees
#37Very intuitive explanation.
Re: Let’s Invent B(+)-Trees
#38I like this approach to describing B-trees! I recently taught B-trees for a data structures course and presented them using a similar method. Thought I'd leave the link in case it was useful: http://web.stanford.edu/class/cs166/lectures/05/Slides05.pdf
Really wonderful presentation, thank you! Especially the way the "animations" (the slides with changes, actually) convey the dynamics in the sequence of events explained.
Re: Let’s Invent B(+)-Trees
#39This is weirdly relevant. I just finished implementing a persistent B-tree library in Scheme.[1][2] I don't know why B-trees aren't used more as a purely-functional data structure. Once they get large enough, they don't move around much when changed; there is no rebalancing except on deletes, and even that only affects the direct path to the deleted node. [1] https://github.com/ar-nelson/schemepunk#b-trees [2] https:…
I like the concept of persistent B-tree, can you share about the storage mechanism?
persistent (for both senses of the word) b-trees are used extensively in couchdb. You can read about their design here:
Re: Let’s Invent B(+)-Trees
#40This sounds exactly how the excellent Python Sorted Containers library works, and achieves "faster than C" performance in pure Python by effective use of the bisect module (which itself is written in C). http://www.grantjenks.com/docs/sortedcontainers/implementati... > The Sorted Containers internal implementation is based on a couple observations. The first is that Python’s list is fast, really fast. Lists have grea…
"Faster than C", by effective use of C? Maybe I'm missing something, but that seems to immediately be a contradiction.
Yeah, you're right. On its homepage it's labelled as "fast as C extensions" and "often faster than C implementations". I guess because C implementations often use inferior data structures -- I used to say "algorithm is better than assembly".