bigeasy / bigeasy/strata

Implement counted b-trees.

Open
#10 6 comments 0 reactions 1 assignee Claimed by @bigeasy View on GitHub
enhancement
Dominant language
JavaScript
Stars
163
Forks
18
PR merge metrics
No merged PRs in 30d

Description

Counted b-trees means that we keep a count for every page, but the user will have to pay for the count, it will be calculated.

When we open a b-tree, we visit all of the leaf pages. All of them. However, we only read from the back of the page to find the the address array so that we can read the address of the next page and the count of records in the file.

Alternatively, we can append this information every time we write a record to the page, or we can append the file position of the last position array written.

You know, that's not a bad idea. As long as we've made the file brittle with file positions, we may as well capitalize on the benefits. Once you've gone and editing a file in Vim, you've pretty much thrown everything off anyway. There will be utilities to tidy a file that you recover in a text editor, essentially a compiler, but once you start poking around with the file, it has become source code. The checksums are off, the file positions are off, etc.

The compiler can play the leaf page as a log and rewrite, reporting failed checksums, but not entirely freaking out and dying, because it's purpose is to rebuild hand edited leaf files. Something that no one should ever do, but possibly a great recovery feature, that you can extract all your data as plain JSON.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.