Indexes: Supercharging Query Performance

Indexes are the key to fast queries in any database. OxiDB uses BTree indexes that maintain sorted order, enabling efficient lookups, range scans, and sorted iteration.

Field Indexes

Create an index on a single field to speed up queries that filter or sort on that field:

from oxidb import OxiDbClient
db = OxiDbClient("127.0.0.1", 4444)

# Create indexes
db.create_index("users", "email")
db.create_index("users", "age")
db.create_index("posts", "created_at")

# These queries now use the index
db.find_one("users", {"email": "[email protected]"})  # O(log n) lookup
db.find("users", {"age": {"$gte": 21, "$lte": 30}})   # index range scan
db.find("posts", {}, sort={"created_at": -1}, limit=10) # index-backed sort

Composite Indexes

Multi-field indexes for queries that filter on multiple fields. OxiDB supports prefix scans on composite indexes:

# Create a composite index on (category, created_at)
db.create_index("products", ["category", "created_at"])

# This query uses the composite index efficiently
db.find("products", {"category": "electronics"}, sort={"created_at": -1})

# Prefix scan — the first field of the composite index is used
db.find("products", {"category": "electronics"})

Text Indexes

Create text indexes for full-text search (covered in detail in the Full-Text Search article):

# Index title and content fields for text search
db.create_text_index("articles", ["title", "content"])

Performance Impact

Here's how indexes affect common operations:

Operation	Without Index	With Index
Find by field	O(n) full scan	O(log n) BTree lookup
Range query	O(n) full scan	O(log n + k) range scan
Sort + limit	O(n log n) sort all	O(limit) iterate index
Count with filter	O(n) scan all	O(1) index set size

OxiDB's index-only count optimization returns the BTreeSet size directly without touching any documents, making filtered counts nearly instant.

Early Termination

Operations like update_one and delete_one stop after the first match. Combined with an index, this means single-document operations are O(log n) regardless of collection size.

How Indexes Work Internally

Each index is a BTreeMap<IndexValue, BTreeSet<DocumentId>>. The IndexValue type enforces cross-type ordering (Null < Bool < Num < DateTime < String), so all values are comparable and sortable within the same tree.

Indexes are maintained in-memory and rebuilt from storage on startup. They're updated synchronously during inserts, updates, and deletes, so they're always consistent with the data.