Repository navigation
refactor(btree): cursor-based scans with seek (v8 PR 1, refs #374) - #442
Merged
Merged
Conversation
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
…ayout Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
…options Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
…ormat spec Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
All B+tree reads go through LeafCursor, which descends with a stack of decoded internal nodes instead of following leaf next_leaf pointers. A copy-on-write tree (#374) cannot keep sibling pointers, so no read path depends on them any more; writers still set them and the format is unchanged. - LeafCursor::new/next/advance_leaf/seek. seek moves forward from the current position: inside the current leaf it binary-searches; otherwise it climbs only to the lowest ancestor whose range covers the key. - range_scan and stream_all_entries use the cursor. collect_leaf_pages walks child pointers depth-first without decoding entries. - Corrupt child pointers: a non-B+tree page is STG-013; a cycle hits MAX_TREE_DEPTH (or the page-count visit bound) as INT-049, never a hang. - find_leaf_for_key removed; find_leftmost_leaf is test-only. Tests: cursor full scan and start positioning, seek against fresh descent (random), monotone seek/next sequences, seek within leaf / to sibling / across subtrees / past end / into the gap after a leaf / backwards, one page read for a seek to the sibling leaf, reads ignore next_leaf, cycle and wrong-page-type handling. Refs #374 #434 Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Descending through an internal node decoded every separator key; the cursor now binary-searches and decodes O(log n) of them, and range_scan borrows entries instead of cloning keys. Upper bounds are read from the path instead of being cloned into each frame. Against v3 (criterion): concurrent_btree_scan/100k -25..-37 %, point_query_chain_depth/sibling_attr/2000 -29 %, checkpoint/after_1_fact/10k -9 %; btree_lookup/entity_point and attribute_scan +2..6 % (~0.4 us). Docs: CHANGELOG (Internal), CLAUDE.md and TEST_COVERAGE.md test counts (1,217 passing, 8 ignored). Refs #374 Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
Codecov Report❌ Patch coverage is
📢 Thoughts on this report? Let us know! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
First of five PRs for the v8 storage format: copy-on-write checkpoints, per-page checksums and covering indexes (#374, #434, #388, #433).
Contents
docs/superpowers/specs/2026-10-05-v8-storage-format-design.md, one spec for all five PRs.docs/superpowers/plans/2026-10-05-v8-storage-format.md. PR 1 is planned in detail; PRs 2–5 are outlined.LeafCursor, which descends from the root and keeps the path as a stack.seekmoves forward from the current position and climbs only to the lowest ancestor that covers the key. No read path follows leafnext_leaflinks any more, because copy-on-write pages can't keep them. Writers still set them, and the file format and query results are unchanged.range_scanandstream_all_entriesuse the cursor.collect_leaf_pageswalks child pointers depth-first without decoding entries.Review focus
cursor_seek_matches_fresh_descent_randomandcursor_seek_sequence_without_reset_visits_ascending_entries.cursor_seek_into_gap_after_leaf_end.cursor_seek_backwards_is_noop.cursor_child_pointing_at_non_btree_page_returns_stg_013andcursor_cycle_in_child_pointers_is_bounded.cursor_seek_to_next_leaf_reads_one_page). Reads are unchanged with everynext_leafzeroed (range_scan_ignores_next_leaf).Benchmarks (criterion, against
v3)concurrent_btree_scan/100k_{2,4,8}tpoint_query_chain_depth/sibling_attr/{500,2000}checkpoint/after_1_fact/10kcheckpoint/after_1_fact/100kbtree_lookup/entity_point/{1k,100k}btree_lookup/attribute_scan/*The
query/*benchmarks use in-memory databases and don't touch this code.Tests
Full suite: 1,217 passing, 8 ignored (+10). Lib clippy is clean. The
clippy --all-targetslints are all intests/*.rsfiles this PR doesn't touch; they were already onv3.Refs #374 #434 #388 #433
🤖 Generated with Claude Code
https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn