B-Tree

A B-Tree automatically maintains balance during insertions and deletions, ensuring all leaf nodes remain at the same depth. This is governed by two key parameters: the minimum degree (t) and the order (m). Each node (except the root) must have at least t-1 keys and at most 2t-1 keys. When a node becomes overfull (a split occurs) or underfull (a merge or redistribution occurs), the tree rebalances by moving keys between sibling nodes or splitting/merging nodes, preserving the logarithmic height guarantee for all operations.

Unlike binary trees where each node has at most two children, a B-Tree node can have many children—often hundreds or thousands. This high branching factor is the key to its disk efficiency. By storing many keys and pointers in a single node, the tree's height is minimized. For example, a B-Tree of order 500 (up to 999 keys per node) can store one billion records in just 3-4 levels. Each disk read fetches an entire node (a page or block), making a single I/O operation retrieve a large number of keys, which drastically reduces the number of expensive disk seeks required for a search.

All keys within a B-Tree node are stored in sorted, ascending order. This sorted organization enables efficient search within a node using binary search (an O(log n) in-memory operation). When traversing the tree, the sorted keys direct the search path: for a target key K, the algorithm compares K to the keys in the current node to select the correct child pointer. This property is essential for supporting range queries and sequential access (in-order traversals), as the sorted structure allows efficient iteration from one key to the next.

B-Trees are explicitly designed to match the characteristics of block-oriented storage devices like HDDs and SSDs. A node is typically sized to fit within a single disk block (e.g., 4KB, 8KB, 16KB). This design minimizes the number of I/O operations:

• Search: Requires O(log_t n) disk reads, where t is the large minimum degree.
• Insert/Delete: May require reading nodes down a path and writing back modified nodes. The algorithms are optimized to perform splits/merges locally, often requiring writes only to the affected node and its parent. This contrasts with in-memory structures like AVL or Red-Black trees, which optimize for comparison count rather than I/O count.

The classic B-Tree stores keys (and often associated data records) in both internal and leaf nodes. However, the B+Tree variant, which is the standard implementation in modern databases (e.g., MySQL InnoDB, PostgreSQL), enhances this for range queries. In a B+Tree:

• Internal nodes store only keys and child pointers (index navigation).
• Leaf nodes store all key-data pairs and are linked together in a doubly-linked list. This separation means sequential scans and range queries only traverse the linked leaf nodes, avoiding the need to revisit the internal tree structure. It also allows for more keys in internal nodes, increasing the branching factor and reducing tree height.

All core B-Tree operations—search, insertion, deletion, and range query—run in O(log n) time, where the base of the logarithm is the large branching factor t. This performance is guaranteed due to the self-balancing property that keeps the tree height-balanced.

• Search: Starts at the root, performs a binary search within a node to choose a subtree, and recurses.
• Insertion: Finds the appropriate leaf, inserts the key, and splits nodes recursively upward if necessary.
• Deletion: More complex; may involve borrowing a key from a sibling or merging nodes, also propagating upward. The actual cost is often measured in disk I/Os (O(log_t n)), which is exceptionally low for large t.

In the context of Agentic Memory and Context Management, B-Trees provide a robust backbone for structured, long-term memory storage where data has inherent order or requires efficient range-based retrieval.

• Episodic Memory Logs: Storing agent experiences or events timestamped sequentially. A B-Tree index on timestamp allows fast retrieval of events from a specific time window.
• Structured Knowledge Lookup: Maintaining an index of known entities (e.g., user IDs, product SKUs, session tokens) for deterministic, fast O(log n) access, complementing probabilistic semantic search in vector stores.
• Metadata Index for Vector Stores: A B-Tree can index metadata fields (e.g., created_at, source_id, type) associated with vector embeddings, enabling hybrid queries that filter by metadata before performing a similarity search.

B-Trees and Log-Structured Merge-Trees (LSM-Trees) are the two dominant structures for disk-based indexes. Their trade-offs dictate system design.

• Write Pattern: B-Trees perform in-place updates, requiring random writes. LSM-Trees use append-only writes, converting random writes to sequential writes, which is often faster on SSDs.
• Read Performance: B-Trees typically offer faster point reads as data is found in a single tree traversal. LSM-Trees may require checking multiple sorted levels (SSTables).
• Space Amplification: B-Trees have lower space overhead. LSM-Trees can have higher write amplification due to background compaction.
• Use Case: Choose B-Trees for workloads with significant range queries or requiring strong, predictable read latency. Choose LSM-Trees for high-volume, write-intensive workloads (e.g., logging, metrics).

The core B-Tree has evolved into optimized variants for specific storage scenarios.

• B+Tree: The most common variant in file and database systems. All data is stored in the leaf nodes, which are linked together in a sequence. Internal nodes only store keys for navigation. This:
  • Maximizes fan-out (more keys per node).
  • Makes range scans and full-table scans extremely efficient.
• B*Tree: Aims to improve node occupancy. Instead of splitting a full node into two half-full nodes, it first tries to redistribute keys to a sibling node. Only if both sibling nodes are full does a three-way split occur. This results in higher average node occupancy (e.g., 66% vs. 50% for a classic B-Tree), reducing tree height and I/O operations.

A write-optimized data structure used in modern storage engines like RocksDB and Apache Cassandra. It batches writes in a memory-resident component (memtable) and periodically flushes sorted runs to disk, which are later merged in the background.

• Key Contrast with B-Trees: LSM-Trees trade slower reads for extremely high write throughput by sequentializing disk writes, whereas B-Trees offer faster reads but incur random writes for updates.
• Use Case: Ideal for agentic systems with high-velocity event logging, telemetry, or append-heavy memory updates where write performance is critical.

A database partitioning technique that horizontally splits a large dataset into smaller, more manageable pieces called shards, which are distributed across multiple servers.

• Relationship to B-Trees: B-Trees often index data within a single shard. Sharding is the strategy for distributing those indexed datasets across a cluster to scale beyond the limits of a single node.
• Agentic Application: Enables the distribution of a massive, persistent agent memory store (e.g., experience logs, knowledge bases) across a fleet of storage nodes for horizontal scalability.

A set of four critical properties—Atomicity, Consistency, Isolation, Durability—that guarantee reliable processing of database transactions.

• B-Tree's Role: B-Trees, combined with write-ahead logging (WAL), are a core mechanism for implementing ACID guarantees in relational databases like PostgreSQL and MySQL. They ensure data remains consistent and recoverable after crashes.
• Importance for Agents: Essential for agentic systems that require deterministic state persistence, such as recording irreversible actions or maintaining a consistent, auditable memory of decisions.

A core database protocol that ensures durability by writing all data modifications to a persistent log file before the changes are applied to the main data structures (like B-Trees).

• Synergy with B-Trees: Provides crash recovery. If the system fails while updating a B-Tree page, the WAL contains the complete record needed to replay the operation and restore consistency.
• Agentic Relevance: A critical component for building fault-tolerant agent memory. It guarantees that no agent experience or learned context is lost due to a system failure.

An algorithm that determines which items to remove from a finite cache when it reaches capacity. Common policies include Least Recently Used (LRU) and Least Frequently Used (LFU).

• Connection to B-Trees: While B-Trees manage on-disk data, their performance relies heavily on in-memory page caches. The eviction policy for this cache (often LRU) directly impacts the efficiency of B-Tree operations.
• Agentic Context: Directly analogous to context window management and memory eviction strategies in AI agents, where decisions must be made about what short-term working memory to retain or discard.

A special hashing technique used in distributed systems to minimize reorganization when nodes are added or removed. It maps both data and nodes to a common hash ring.

• Comparison to B-Trees: While B-Trees provide ordered indexing on a single machine, consistent hashing provides a distributed lookup mechanism to locate which node (which may use a B-Tree internally) is responsible for a given piece of data.
• System Design Link: A foundational pattern for building scalable, sharded vector databases and key-value stores that serve as the persistence layer for distributed multi-agent systems.