Free sample lesson ยท Understanding VireoDB Storage Mechanics
Range Scans
How does sorting keys make scanning contiguous records fast?
Lesson 1 of the Wondering course Understanding VireoDB Storage Mechanics
Why Ordered Keys Help
A range scan looks for records between two key values.
When keys stay sorted, nearby values remain together in key order. The engine can move through a contiguous sequence instead of searching randomly.
Notice how a sorted leaf-page path lets the engine move through nearby keys, unlike random searching across scattered records.
VireoDB stores integer keys in leaf pages. Maintaining their order makes scanning a range more direct.
When A Page Fills
Each VireoDB leaf page holds exactly four integer keys.
Suppose a full page contains [10, 20, 30, 40]. Inserting 25 would break the page limit and disturb its sorted structure.
VireoDB uses copy-on-write splitting. It keeps the old page unchanged and creates new pages for the updated order.
The Split In Action
The inserted key 25 belongs between 20 and 30.
VireoDB allocates two new leaf pages: [10, 20, 25] and [30, 40]. Both pages preserve sorted order, while the original [10, 20, 30, 40] stays immutable.
This split writes two new data pages for one logical insert.
- Find position: Place the inserted key 25 between 20 and 30 to preserve key order.
- Create pages: Allocate two new leaf pages containing [10, 20, 25] and [30, 40].
- Keep original: Leave [10, 20, 30, 40] immutable while the two new pages represent the updated order.
Understanding The Trade-Off
For this toy accounting, data-page write amplification means new data pages written per logical insert.
The example writes 2 pages for 1 insert, so the amplification is 2x. Copy-on-write protects the old page, but it requires extra page creation.
Parent-page writes and log writes are excluded. Do not generalize this VireoDB behavior to other database engines.
- New data pages: Two new data pages are written for the example insert.
- Logical inserts: The accounting covers one logical insert.
- Write amplification: The ratio is 2 new data pages per logical insert.
- Protection
- Old page stays unchanged: Copy-on-write protects the original data page.
- Sorted order preserved: The newly created pages maintain the key order.
- Trade-off
- Extra page creation: The protection requires writing two new data pages.
- Limited accounting scope: Parent-page writes and log writes are excluded, and the behavior should not be generalized to other database engines.
Toy accounting for this VireoDB example only.
Check yourself
When keys remain sorted, a range scan can move through nearby records in a contiguous sequence.
- True
- False
Answer: True
Sorted keys keep nearby values together, so the engine can scan through an ordered sequence instead of searching randomly.
Choose from: range scan; copy-on-write splitting. A _____ searches between key values, while _____ creates new pages and preserves the old page.
Answer: Choose from: range scan; copy-on-write splitting. A range scan searches between key values, while copy-on-write splitting creates new pages and preserves the old page.
A range scan is an operation for finding records between keys. Copy-on-write splitting updates page structure by creating new pages while leaving the old page unchanged.
How many integer keys can one VireoDB leaf page hold?
- Two
- Three
- Four
- Eight
Answer: Four
Each VireoDB leaf page holds exactly four integer keys.
Keep going
This is lesson 1 of 4 in Understanding VireoDB Storage Mechanics. Next up:
- Leaf Capacity
- Page Splitting
- Write Amplification
Wondering turns any topic into short lessons you can read, watch, or listen to, with practice questions and an AI tutor.