1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
On-disk file format and data structure
======================================
Larch B-tree forests are stored on the disk as follows:
* Each forest is stored in a separate directory tree structure.
* The file ``metadata`` is in the INI format, and stores metadata about
the forest, including the identifiers of the root nodes of the trees.
* The ``nodes`` directory contains the actual nodes.
* The ``refcounts`` directory contains reference counts for nodes.
The metadata file
-----------------
The following values are stored in the metadata file:
* ``format`` is ``1/1``: node store format version 1 and node codec version 1.
* ``node_size`` is the maximum size of an encoded node, in bytes.
* ``key_size`` is the size of the keys, in bytes.
* ``last_id`` is the latest allocated node identifier in the forest.
* ``root_ids`` lists the identifiers of the root nodes of the trees.
Node files
----------
Leaf nodes are encoded as follows:
* the first four bytes are 'O', 'R', 'B', 'L'
* 64-bit unsigned integer giving the node identifier
* 32-bit unsigned integer giving the number of key/value pairs
* all keys catenated
* lengths of values as 32-bit unsigned integers
* all values catenated
Index nodes are encoded as follows:
* the first four bytes are 'O', 'R', 'B', 'I'
* 64-bit unsigned integer giving the node identifier
* 32-bit integer giving the number of keys
* all keys catenated
* all child ids catenated, where each id is a 64-bit unsigned integer
All integers are in big-endian order.
All root nodes are index nodes, so decoding can start knowing that
the first node is an index node.
Each node is stored in a file under the ``nodes`` subdirectory,
using multiple levels of directories to avoid having too many files
in the same directory. The basename of the file is the node identifier
in hexadecimal.
The directory levels are user adjustable, see the ``IdPath`` class
for details.
Reference counts
----------------
Each node has a reference count. When the count drops to zero, the
node file gets removed. Reference counts are stored in files under
the ``refcounts`` subdirectory. Each file there contains up to
32768 reference counts, as a 16-bit unsigned big-endian integer.
Thus, the reference count for node i is file named ``refcount-N``
where N is i modulo 32768.
A refcount file that is full of zeroes is removed. When looking up
refcounts, if the file does not exist, the count is assumed to be zero.
This avoids having to store refcounts for deleted nodes indefinitely.
|
