mirror of
https://github.com/featurebasedb/featurebase.git
synced 2026-08-28 10:54:59 +00:00
206 lines
4.7 KiB
Markdown
206 lines
4.7 KiB
Markdown
Roaring B-tree Format
|
|
=====================
|
|
|
|
The RBF format represents a Roaring bitmap whose containers are stored in the
|
|
leafs of a b-tree. This allows the bitmap to be efficiently queried & updated.
|
|
|
|
|
|
## File Format
|
|
|
|
The RBF file is divided into equal 8KB pages. Each page after the meta page
|
|
is numbered incrementally from 1 to 2^31.
|
|
|
|
Pages can be one of the following types:
|
|
|
|
- Meta page: contains header information.
|
|
- Branch page: contains pointers to lower branch & leaf pages.
|
|
- Leaf page: contains array and RLE container data.
|
|
- Bitmap page: contains bitmap container data.
|
|
|
|
All integer values are little endian encoded.
|
|
|
|
|
|
## Page header
|
|
|
|
Every page type except the bitmap page contains the following header:
|
|
|
|
[4] page number
|
|
[4] flags (indicates the type of the page)
|
|
|
|
### Meta page
|
|
|
|
The meta page contains the following header:
|
|
|
|
[4] magic (\xFFRBF)
|
|
[4] flags
|
|
[4] page count
|
|
[8] wal ID
|
|
[4] root records pgno
|
|
[4] freelist pgno
|
|
|
|
|
|
### Root Records page
|
|
|
|
A list of all b-tree names & their respective root page numbers are stored in
|
|
root record pages. Once a bitmap root is created, it is never moved so the
|
|
root record pages only need to be rewritten when creating, renaming, or deleting
|
|
a b-tree. If records exceed the size of a page then they are overflowed to
|
|
additional pages.
|
|
|
|
[4] page number
|
|
[4] flags
|
|
[4] overflow pgno
|
|
[*] bitmap records
|
|
|
|
Each bitmap record is represented as:
|
|
|
|
[4] pgno
|
|
[2] name size
|
|
[*] name
|
|
|
|
All bitmap records are loaded into memory when the file is opened.
|
|
|
|
|
|
### Branch page
|
|
|
|
The branch page contains the following header:
|
|
|
|
[4] page number
|
|
[4] flags
|
|
[2] cell count
|
|
[*] cell index (2 * cell count)
|
|
[*] padding for 4-byte alignment
|
|
|
|
Each cell is formatted as:
|
|
|
|
[8] highbits
|
|
[4] flags
|
|
[4] page number
|
|
|
|
|
|
### Leaf page
|
|
|
|
The leaf page contains the following header:
|
|
|
|
[4] page number
|
|
[4] flags
|
|
[2] cell count
|
|
[*] cell index (2 * cell count)
|
|
|
|
|
|
The leaf page contains a series of cells with the header of:
|
|
|
|
[8] highbits
|
|
[4] flag
|
|
[4] child count
|
|
[*] array or RLE data or Handle (a pageno) to Bitmap Data
|
|
|
|
|
|
### Bitmap Data page
|
|
|
|
The data for the bitmap data page takes up the entire 8KB.
|
|
|
|
|
|
## Proof of Concept Notes
|
|
|
|
The following are notes made that are temporary for the RBF format. This will
|
|
change as development progresses:
|
|
|
|
- Transaction support is deferred
|
|
- WAL support is deferred
|
|
|
|
|
|
## Pattern of branch splits when adding data in ascending sorted order.
|
|
|
|
In this example, fan-out is restricted to 2 to make the
|
|
drawings easy and the splits obvious. The data leaves are only allowed one
|
|
roaring.Container key (ckey) in this example.
|
|
|
|
Each frame adds the next datum: A,B,C,D,E,... in order.
|
|
|
|
The letter represent data leaves, while
|
|
numbers represent branch pages. The one exception is the
|
|
first frame where the root is a leaf with data.
|
|
Every frame after has normal branch at the root.
|
|
|
|
NB: there are only three places pages get written on addition:
|
|
a) writeRoot
|
|
b) putLeafCell
|
|
c) putBranchCells
|
|
|
|
---------------------------------------------
|
|
add A:
|
|
root
|
|
3
|
|
A
|
|
---------------------------------------------
|
|
add B:
|
|
root
|
|
3
|
|
4 5
|
|
A B
|
|
---------------------------------------------
|
|
add C: this sequence of updates occurs
|
|
|
|
1) putLeafCell writes leaf B to page 5
|
|
2) putLeafCell writes leaf C to page 6
|
|
3) putBranchCells writes branch page 7 with children 4,5
|
|
4) putBranchCells writes branch page 8 with child 6
|
|
5) writeRoot writes branch cells to pgno 3, children: 7,8
|
|
|
|
root
|
|
3
|
|
7 8
|
|
4 5 6
|
|
A B C
|
|
---------------------------------------------
|
|
add D:
|
|
root
|
|
3
|
|
7 8
|
|
4 5 6 9
|
|
A B C D
|
|
|
|
---------------------------------------------
|
|
add E:
|
|
root
|
|
3
|
|
12 13
|
|
7 8 11
|
|
4 5 6 9 10
|
|
A B C D E
|
|
---------------------------------------------
|
|
add F:
|
|
root
|
|
3
|
|
12 13
|
|
7 8 11
|
|
4 5 6 9 10 14
|
|
A B C D E F
|
|
---------------------------------------------
|
|
add G:
|
|
root
|
|
3
|
|
12 13
|
|
7 8 11 16
|
|
4 5 6 9 10 14 15
|
|
A B C D E F G
|
|
---------------------------------------------
|
|
add H:
|
|
root
|
|
3
|
|
12 13
|
|
7 8 11 16
|
|
4 5 6 9 10 14 15 17
|
|
A B C D E F G H
|
|
---------------------------------------------
|
|
add I:
|
|
root
|
|
3
|
|
21 22
|
|
12 13 20
|
|
7 8 11 16 19
|
|
4 5 6 9 10 14 15 17 18
|
|
A B C D E F G H I
|
|
---------------------------------------------
|
|
|