Adrian Cochrane @alcinnz@floss.social

Ford Foundation's Road & Bridges discussed the topic of a "post open source".

And yet I think if you strip away the facade of people not licensing their work properly, repeatedly reimplementing the same infrastructure, or developing exclusively for proprietary platforms I don't think things have changed that much from a decade ago.

"Open source has been such an incredible force for quality and community exactly because it's not been de ned in market terms. In market terms, most open source projects should never have had a chance."
– David Heinemeier Hansson, Ruby on Rails
Via Ford Foundation's "Roads & Bridges"

There's essentially two type of BTrees.

Ordinary BTrees stores the values in the same pages as their corresponding keys.

B+Trees make range, prefix, & sorting queries at a negligable cost to lookups, deletes, & inserts. By making the leaves hold the values, and references the next & previous leaf pages in sorted order.

This makes it very quick to quickly find which page to add, remove, lookup a key in. And upon overflow it can just split the page in half separated by a single key added to the parent, an approach which has the nice byproduct of keeping the tree "balanced" and performance constant.

And once you've found a key it makes it easy to iterate over all keys greater than or less then it. Also range & prefix queries.

Most SQL operators are blazingly fast with that, though only for one column per table.

While it is generally exposed to apps as a stream of bytes, hard disks are split up into "pages" that are copied into memory as needed. And while SRAM has less need of this, it still helps reduce bus congestion if they can copy out large sections at a time.

In each of these pages belonging to it a BTree will store a bunch of sorted keys (and maybe values) alongside references to the pages storing keys between each sequential pair of keys.

I've described RDBMSs before as interpreted languages distinguished with an AI optimizer.

But runtime most of them are heavily based to some extent or other on BTrees (PostgreSQL has them as it's default index, & SQLite stores everything in them).

BTrees are a datastructure that makes it trivial to sort, test for presence of, or lookup data. And one that naturally and efficiently fits on a harddisk.

That is BTrees are an implementation of a "sorted mapping".

I've heard people in talks be excited about a future without filesystems. It never excited me, but now I don't think I like the idea.

I can see it feeling pointless, but having to write the code that persists a program's data forces us to think about the issue. And it pushes us to make our data accessible long after our software goes extinct.

Because data reliably outlives software.