Module sanakirja_core::btree::page

Expand description

Implementation of B tree pages for Sized types, i.e. types whose representation has a size known at compile time (and the same as core::mem::size_of()).

The details of the implementation are as follows:

The page starts with a 16 bytes header of the following form (where all the fields are encoded in Little-Endian):

#[repr(C)]
pub struct Header {
    /// Offset to the first entry in the page, shifted 3 bits
    /// to the right to allow for the dirty bit (plus two
    /// extra bits, zero for now), as explained in the
    /// documentation of CowPage, at the root of this
    /// crate. This is 4096 for empty pages, and it is unused
    /// for leaves. Moreover, this field can't be increased:
    /// when it reaches the bottom, the page must be cloned.
    data: u16,
    /// Number of entries on the page.
    n: u16,
    /// CRC (if used).
    crc: u32,
    /// The 52 most significant bits are the left child of
    /// this page (0 for leaves), while the 12 LSBs represent
    /// the space this page would take when cloned from scratch,
    /// minus the header. The reason for this is that entries
    /// in internal nodes aren't really removed when deleted,
    /// they're only "unlinked" from the array of offsets (see
    /// below). Therefore, we must have a way to tell when a
    /// page can be "compacted" to reclaim space.
    left_page: u64,
}

For leaves, the rest of the page has the same representation as an array of length n, of elements of type Tuple<K, V>:
```
#[repr(C)]
struct Tuple<K, V> {
    k: K,
    v: V,
}
```
If the alignment of that structure is more than 16 bytes, we need to add some padding between the header and that array.
For internal nodes, the rest of the page starts with an array of length n of Little-Endian-encoded u64, where the 12 least significant bits of each u64 are an offset to a Tuple<K, V> in the page, and the 52 other bits are an offset in the file to the right child of the entry.

Moreover, the offset represented by the 12 LSBs is after (or at) header.data. We say we can “allocate” in the page if the data of the header is greater than or equal to the position of the last “offset”, plus the size we want to allocate (note that since we allocate from the end of the page, data is always a multiple of the alignment of Tuple<K, V>).

Structs§

Page
Empty type implementing BTreePage and BTreeMutPage.