Strata 0.0.3

Far-Off Buttes by BrotherMagneto

Installing Strata 0.0.3

npm install b-tree

Directory Now In options

Moved the sparate directory argument into the options hash. It doesn't look right to have the options hash optional. Most of those options do not go unspecified in any serious application of Strata.

Support for Random Inserts

If you have a list your merging into the tree, but you've not sorted it, you can still have a go at inserting the next item in your list into the current page under your cursor. Previously, Strata would assert that the inserted record's key was greater than the key of the current leaf page, but now it is not so shrill. It returns an error, a -1 to let you know that the key belongs in a leaf page to the left of the current page. That's useful if you're table scanning for reasons detailed in the Which Way To Go section below.

Increased Liveness of Inserts

Peek right gets key and immediately releases lock.

The peek at the right leaf page on insert to resolve ambiguity about the proper page for a key that greater than the greatest key in the leaf page no longer obtains and holds an exclusive lock. Instead it get key using a shared lock and immediately releases the shared lock.

The key of the right leaf page might change. It might get deleted. If it is deleted it is now a ghost. That ghost might get exorcised (permanently deleted) This would change the key of the right sibling leaf page, making the results for our of inclusion different. It would seem that different is bad, so let's hold that write lock because I fear change. We all do.

The key value for the leaf page is the first record in the key page. It is therefore, the least value of that key page. When you exorcise a ghost of a leaf page, the key value can only increase. If the leaf page key of the right leaf page changes it does not invalidate any of the tests performed against the deleted value. They are all still less than the key of the right leaf page.

After we cache the key of the right leaf page and the key of the right leaf page changes, subsequent tests might falsely report that a record does not belong on the current page. When this happens, the user is going to descend the tree again to find the correct leaf page, which is always a safe bet. It's a missed opportunity to insert the record while we're there, but it's not going to cause corruption. It's likely going to be rare and we've decided that descents are cheap and the path we take when in doubt.

This is an increase in liveness. Leaf page mutation will only ever hold and exclusive lock on a single leaf page. It will only occasionally obtain an additional shared lock and then release it immediately.

Cursor.insert Let's You Know Which Way To Go

There is case where we fail because our cached key says we fail, but we're navigating with a sorted list of items to insert and delete, so we advance to the next leaf page hoping to see if we can insert there, but we're told we fail again. If we've chosen a table scan for our approach we will continue to fail until we get to the end of the tree.

The more likely approach means that after two failures we will descend again, but if you need to know for certain we now simply return an integer to indicate failed, on that let's you know which way to go. If you advanced to the next page because an insert failed, but then it says it fails again because the key is to low, you know you lost a race and need to stop your table scan and descend again using the key that's causing the confusion.

Issue By Issue

• Upgrade Proof to 0.0.31. #113.
• Return an comparative integer from Cursor.insert. #112.
• Peek of next page during insert with read lock, release immediately. #111.
• Mutator should return false if index is to low instead of asserting. #110.
• All Strata constructor options should be in the options hash. #109.
• Fix aspect ratio of README.md image. #108.

Up Next / Strata 0.0.4

The next exciting update for Strata will be the release of Locket a pure-JavaScript b-tree implementation of a LevelUP backend. Whatever Locket wants Locket gets. Then, when Locket is built, I'll be using LevelUp unit tests and benchmarks for choose the next actions for Strata.

Have a look at the discussion that inspired Locket to get a feel for where we're going.