BPTreeV1 class abstract

Represents a B+-tree node with sorted, arbitrary length key-value pairs, key compression and offset index.

The structure starts with the following:

Node identification (always present):

  • uint8[3]: `0xab`, `0xf4`, `0x70` - first 3 bytes of the md5 hash of bptree/v1.
  • uint8 byte - internal version and endian-ness
    • bits 0-6 - the minimum internal version required to parse the bytes
    • bit 7: the endian-ness of the multi-byte encodings (0: little-endian, 1: big-endian).

Node options (always present):

  • uint8 byte
    • bit 0: whether custom data is present
    • bit 1: whether entries are sorted
    • bit 2: whether key compression is present
    • bit 3: whether offset index is present
    • bits 4-7: reserved for future use.
  • varint for the number of entries

Custom data (when flag is set):

  • varint for bytes length
  • uint8[] containing the custom data

Key compression (when flag is set):

  • varint for prefix bytes length
  • uint8[] containing the prefix bytes
  • varint for postfix bytes length
  • uint8[] containing the postfix bytes

NOTE: The keys inside this node will be stored without the given prefix or postfix.

Offset index (when flag is set):

  • uint8 byte
    • bit 0-1: size code
      • 0: uint8 1-byte index
      • 1: uint16 2-bytes index
      • 2: uint32 4-bytes index
      • 3: uint64 8-bytes index
    • bit 2: whether there is an item count for this index (or it will use a previously defined count if there is any)
    • bit 3: whether start offset is padded to offset dividible by 8.
    • bits 4-7: reserved for future use (sparse index specification)
  • (optional) varint - the number of entries in the position index (if the flag above is set)
  • (optional) uint8[] padding 0x00 (zero) bytes so that index starts at offset divisible by 8
  • uint8[] position index bytes

Key-value entries (always present):

  • uint8: key and value length specification
    • bits 0-2: the length encoding of keys:
      • 0: length is prefixed with a 1-byte uint8
      • 1: length is prefixed with a 2-bytes uint16
      • 2: length is prefixed with a 4-bytes uint32
      • 3: length is prefixed with a 8-bytes uint64
      • 4: length is prefixed with a varint value
      • 5-6: reserved for future use
      • 7: length is const, specified with a follow-up varint value
    • bits 3-5: the length encoding of values (see values for keys).
    • bit 6: whether start offset is padded to offset dividible by 8.
    • bit 7: reserved for future use
  • (optional) varint for const key length (if key encoding code is 7)
  • (optional) varint for const value length (if value encoding code is 7)
  • varint total bytes length of the entries
  • (optional) padding 0x00 (zero) bytes so that the entries start at an offset dividible by 8.
  • entries encoded as
    • key length prefix (or absent for const key length) depending on the key length encoding
    • key bytes
    • value length prefix (or absent for const value length) depending on the value length encoding
    • value bytes

NOTE: there is no end marker for key-value entries, the last entry ends at the last byte.

Implemented types

Constructors

BPTreeV1()

Properties

hashCode → int
The hash code for this object.
no setterinherited
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited

Methods

getValue(List<int> key) → Uint8List?
Returns the corresponding value of key.
inherited
listKeys() → Iterable<Uint8List>
List keys that are part of the data structure.
inherited
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
toString() → String
A string representation of this object.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited

Static Methods

build(Iterable<MapEntry<List<int>, List<int>>> entries, {Endian? endian, List<int>? customData, bool? keepEntryOrder, bool? skipOffsetIndex, bool? usePadding}) → Uint8List
parse(Uint8List bytes) → BPTreeV1