BTree Index¶

The BTree index is a two-level structure that provides efficient range queries and sorted access. It strikes a balance between an expensive memory structure containing all values and an expensive disk structure that can't be efficiently searched.

The upper layers of the BTree are designed to be cached in memory and stored in a BTree structure (page_lookup.lance), while the leaves are searched using sub-indices (page_data.lance, currently just a flat file). This design enables efficient memory usage - for example, with 1 billion values, the index can store 256K leaves of size 4K each, requiring only a few MiB of memory (depending on data type) for the BTree metadata while narrowing any search to just 4K values.

Index Details¶

message BTreeIndexDetails {

}

Storage Layout¶

The BTree index consists of two files:

1. page_lookup.lance - The BTree structure mapping value ranges to page numbers
2. page_data.lance - The actual sub-indices (flat file) containing sorted values and row addresses

Page Lookup File Schema (BTree Structure)¶

Schema Metadata¶

Page Data File Schema (Sub-indices)¶

Stable Row ID Reverse Lookup¶

An ordinary BTree may index the logical _rowid column of a table, given the following rules:

• Stable Row IDs must be enabled on the table.
• IndexMetadata.fields must be a single field ID -3.
• _rowid must be represented as a non-nullable UInt64 field.
• The index must use the address-domain format and be at least version 1.

The logical field need not appear in the user schema. Its inline and spilled representations are defined in Row ID and Lineage.

Accelerated Queries¶

The BTree index provides exact results for the following query types: