dissect.database.ese.btree

Module Contents

Classes

BTree

A simple implementation for searching the ESE B+Trees.

Functions

find_node

Search a page for a node matching key.
class dissect.database.ese.btree.BTree(db: dissect.database.ese.ese.ESE, root: int | dissect.database.ese.page.Page)

A simple implementation for searching the ESE B+Trees.

This is a stateful interactive class that moves an internal cursor to a position within the BTree.

Parameters:

  • db – An instance of ESE.

  • page – The page to open the BTree on.

db
root
reset() → None

Reset the internal state to the root of the BTree.

node() → dissect.database.ese.page.Node

Return the node the BTree is currently on.

Returns:

A Node object of the current node.

next() → dissect.database.ese.page.Node

Move the BTree to the next node and return it.

Can move the BTree to the next page as a side effect.

Returns:

A Node object of the next node.

next_page() → None

Move the BTree to the next page in the tree.

Raises:

NoNeighbourPageError – If the current page has no next page.

prev() → dissect.database.ese.page.Node

Move the BTree to the previous node and return it.

Can move the BTree to the previous page as a side effect.

Returns:

A Node object of the previous node.

prev_page() → None

Move the BTree to the previous page in the tree.

Raises:

NoNeighbourPageError – If the current page has no previous page.

search(key: bytes, exact: bool = True) → dissect.database.ese.page.Node

Search the tree for the given key.

Moves the BTree to the matching node, or on the last node that is less than the requested key.

Parameters:

  • key – The key to search for.

  • exact – Whether to only return successfully on an exact match.

Raises:

KeyNotFoundError – If an exact match was requested but not found.

dissect.database.ese.btree.find_node(page: dissect.database.ese.page.Page, key: bytes) → int

Search a page for a node matching key.

Referencing Extensible-Storage-Engine source, they bail out early if they find an exact match. However, we prefer to always find the _first_ node that is greater than or equal to the key, so we can handle cases where there are duplicate index keys. This is important for “range” searches where we want to find all keys matching a certain prefix, and not end up somewhere in the middle of the range.

Parameters:

  • page – The page to search.

  • key – The key to search.

Returns:

The node number of the first node that’s greater than or equal to the key.