Skip to main content

Indexes

Overview​

Indexes are supplementary data structures built on a column or set of columns in a blockchain schema. When a blockchain is mutated, all indexes on the blockchain are mutated accordingly. bSQL offers an array of different indexes to support auditing, enforce constraints, and improve query speeds.

Terminology

key: The values in a record corresponding to the column(s) that the index was built on.

tree: The bPlus tree data structure that provides the underlying mechanics of an index.

state index: Refers to the primary key index required for all blockchain types except HISTORICAL.

user-defined: Indexes built in the index clause of a CREATE BLOCKCHAIN statement, or added to a blockchain using the CREATE INDEX command.

Index Types

PRIMARY KEYS​

  • HISTORICAL PLUS: Uses a secondary index to reference a record's position on the page.

    ↳ A single secondary index is referenced by both blockchains when two or more HISTORICAL PLUS blockchains are shared.

  • TRADITIONAL and SPARSE: Use a multi-version that optimizes the retrieval of previous database versions without impacting performance on the current state of the system.

    ↳ A single multi-version index is referenced by both blockchains when two or more TRADITIONAL or SPARSE blockchains are shared.

UNIQUE​

This column constraint uses a single secondary index to enforce the unique constraint.

USER-DEFINED​

User-defined indexes can be built on blockchains to optimize storage and retrieval. Available user-defined indexes are listed below:

ALT1​

Indexes of type ALT1 are the most basic index and are kept internally on columns with primary key and unique constraints. Additionally, user-defined ALT1 indexes are used to enforce uniqueness over column(s) and provide speedups for specific queries.

Main Idea​

  • Trees store key → record pairs at their leafs and keys are traversed in sorted order.
  • Enforces uniqueness across keys, and will error if a mutation violates this constraint.
  • Provides sorted scans for query optimization.

ALT2​

Indexes of type ALT2 are only offered as a user-defined index option, and aren't kept internally. They are similar to ALT1 indexes but require an extra IO for record retrieval, but are more space efficient.

Main Idea​

  • Trees store key → recordId pairs at their leafs and IDs are traversed in key order.
  • Enforces uniqueness, and will error if a mutation violates this constraint.
  • Provide quick access to memory locations for record lookup.

ALT3​

Indexes of type ALT3 track all mutations on primary on the specified key. As a whole, they are similar to ALT1 indexes but instead of storing a single record at the leaf level, they use a series of cluster pages to store key histories.

Main Idea​

  • Trees store key → record history at their leafs.
  • Provide access to the record history of a specific key.
  • Provide access to the mutation history of a blockchain.

User-Defined ALT3​

It is important to note that user-defined indexes do enforce uniqueness on the keys in which they are defined. They track updates to the key, and reflect the current state of the specified column(s) with additional access to key history.

ALT3RID​

Indexes of type ALT3 are only offered as a user-defined index, enforce uniqueness, and aren't used internally. They function similarly to an ALT3 index but store mutated recordId's instead of whole records. They require an extra IO for record retrieval, but are more space efficient if the record size is smaller than 12 bytes.

Main Idea​

  • Trees store key → recordId history at their leafs.
  • Provide access to the recordId history of a specific key.
  • Enforce uniqueness.

See Also​