Implement `copacetic`.
- Dominant language
- JavaScript
- Stars
- 163
- Forks
- 18
- PR merge metrics
- No merged PRs in 30d
Description
About to add to a test a traversal where I ensure that the levels are linked correctly and the children are linked correctly. This is the `copacetic` method I've been meaning to create. Here are some thoughts.
To prevent `copacetic` from ruining the cache, we can add a parameter to `IO.lock` that will not relink a page. We would link newly created pages to the end of the most-recently used list. Then if we're not the `copacetic` function, we'd relink all pages visited to the head of the most-recently used list.
Or else, we can just count on the most-recently used cache to work correctly in any case.
We can mark leaf pages with an extension. With a simple directory listing, we will know all the addresses of the leaf pages. A correct b-tree will arrange those pages into a linked list. We'll also know all the branch pages. We can keep an associative array of these addresses, deleting them as they are visited and correctly linked.
Have you considered a branches directory and a leaves directory? Do you like that idea?
Alternatively, we can simply list the directory and obtain all addresses and ensure that each address is visited.
Each page must be referenced by one left sibling, unless it is the left most page of a level. Each page must be referenced by one parent, unless it is the root.
The leaf pages must have their records in the collation order. The leaf pages must be in collation order. The first record of a right sibling leaf page must be greater than the last record of a left sibling leaf page.
Replaying a leaf page as a journal must encounter no invalid checksums, no breaks in the journal entry number and must produce a page identical to the page loaded by `readLeaf`.
Do we want to create a b-tree wide cache of leaf page keys? How big would that get? We might want to do this for the sake of the `copacetic` function, local to the `copacetic` function. Then why not have the tree structure in memory always?
The keys of branch pages should be in ascending order. The leaf page key of the first child of a branch page should be less than all other keys in the branch page. The last key in a branch page should be less than the leaf page key of the first child of its right sibling branch page.
Run this function after every balance.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.