B+ Tree with Transactional Support

🎉 Production-ready B+ Tree implementation with full transactional support, Copy-on-Write operations, and 2PC (Two-Phase Commit)

✨ Features

• 🚀 Zero dependencies - Pure TypeScript implementation
• 📦 Multiple build formats - ESM, CommonJS, and TypeScript source support
• 🔄 Full transactional support with ACID properties
• 📝 Copy-on-Write (CoW) operations for data integrity
• 🔒 Two-Phase Commit (2PC) for distributed transactions
• 💾 Savepoint support for fine-grained transaction control
• 🔍 Snapshot isolation between concurrent transactions
• 📊 Duplicate keys support for non-unique indexes
• ⚡ High performance with optimized B+ tree operations
• 🛡️ Type-safe with full TypeScript support
• 🧪 100% test coverage (373/373 tests passing)

📋 Table of Contents

• Installation
  • Build Formats
  • Usage Examples by Environment
• Exports
• Quick Start
• API Reference
  • Basic Operations
  • Transactional Operations
  • Two-Phase Commit (2PC)
• Savepoint Support
• Serialization and Persistence
• Advanced Examples
• Complex Indexes and Composite Keys
• Query Operations
• Performance Characteristics
• Type Safety
• Configuration Options
• Error Handling
• Contributing

📦 Installation

Versioning note: The adapter is available since 1.3.x. For older versions, upgrade recommended or provide your own compatibility layer.

npm install b-pl-tree
# or
yarn add b-pl-tree
# or
bun add b-pl-tree

📦 Build Formats

The library is available in multiple formats to support different environments:

Environment/Interop Notes:

• ESM: import { BPlusTree } from 'b-pl-tree' — the adapter selects the best (de)serialization strategy.

• CommonJS: const { BPlusTree } = require('b-pl-tree') — same adapter behavior.

• Bun (TypeScript source): direct TS import, adapter logic identical.

• ESM (ES Modules): ./dist/index.esm.js - For modern bundlers and Node.js with "type": "module"

• CommonJS: ./dist/index.js - For traditional Node.js and older bundlers

• TypeScript: ./src/index.ts - Direct TypeScript source (when using Bun)

• Type Definitions: ./types/index.d.ts - Full TypeScript type support

The package automatically selects the appropriate format based on your environment:

{
  "exports": {
    ".": {
      "types": "./types/index.d.ts",
      "bun": "./src/index.ts",
      "import": "./dist/index.esm.js",
      "require": "./dist/index.js"
    }
  }
}

Usage Examples by Environment

ES Modules (Node.js with "type": "module" or modern bundlers)

import { BPlusTree } from 'b-pl-tree'

CommonJS (Traditional Node.js)

const { BPlusTree } = require('b-pl-tree')

Bun (Direct TypeScript)

import { BPlusTree } from 'b-pl-tree' // Uses TypeScript source directly

📤 Exports

The library provides comprehensive exports for all functionality:

Core Classes and Types

import {
  BPlusTree,           // Main B+ tree class
  Node,                // Node class for tree structure
  TransactionContext,  // Transaction management

  // Type definitions
  PortableBPlusTree,   // Serializable tree format
  ValueType,           // Supported key types (number | string | boolean)
  PortableNode,        // Serializable node format
  ITransactionContext, // Transaction interface
  SavepointInfo,       // Savepoint information interface
  SavepointSnapshot,   // Savepoint snapshot interface
  Comparator,          // Comparator function type
  Transaction,         // Transaction function type
  Cursor               // Query cursor type
} from 'b-pl-tree'

Serialization Utilities

import {
  serializeTree,       // Convert tree to portable format
  deserializeTree,     // Load data into existing tree
  createTreeFrom       // Create new tree from data
} from 'b-pl-tree'

Adapter Quick Start

import { serializeTree, deserializeTree } from 'b-pl-tree'

// Serialize your tree
const portable = serializeTree(tree)

// Restore a new tree instance
const restored = deserializeTree(portable)

Migration Notes (from static API)

- const data = BPlusTree.serialize(tree)
- const restored = BPlusTree.createFrom(data)
+ const data = serializeTree(tree)
+ const restored = deserializeTree(data)

Query System

import {
  query,               // Main query function

  // Query operators
  map,                 // Transform data
  filter,              // Filter data
  reduce,              // Aggregate data
  forEach,             // Execute side effects

  // Source functions
  sourceEach,          // Iterate all items
  sourceEq,            // Find exact matches
  sourceGt,            // Find greater than
  sourceLt,            // Find less than
  sourceRange,         // Find within range

  // Action functions
  remove,              // Remove operations

  // Evaluation utilities
  executeQuery         // Execute query pipeline
} from 'b-pl-tree'

Utility Functions

import {
  print_node,                    // Debug tree structure
  compare_keys_primitive,        // Compare primitive keys
  compare_keys_array,           // Compare array keys
  compare_keys_object           // Compare object keys
} from 'b-pl-tree'

Complete Import Example

// Import everything you need
import {
  BPlusTree,
  TransactionContext,
  serializeTree,
  deserializeTree,
  query,
  filter,
  map,
  type ValueType,
  type Comparator,
  type SavepointInfo
} from 'b-pl-tree'

// Ready to use!
const tree = new BPlusTree<User, number>(3, false)
const txCtx = new TransactionContext(tree)

// Example with savepoints
async function exampleWithSavepoints() {
  // Create savepoint
  const savepointId = await txCtx.createSavepoint('checkpoint')

  // Make changes
  tree.insert_in_transaction(1, { id: 1, name: 'Alice' }, txCtx)

  // Get savepoint info
  const info: SavepointInfo | undefined = txCtx.getSavepointInfo(savepointId)
  console.log('Savepoint info:', info)

  // Rollback if needed
  await txCtx.rollbackToSavepoint(savepointId)

  // Commit transaction
  await txCtx.commit()
}

🚀 Quick Start

import { BPlusTree } from 'b-pl-tree'

// Create a B+ tree with minimum degree 3, allowing duplicates
const tree = new BPlusTree<string, number>(3, false)

// Basic operations
tree.insert(10, 'ten')
tree.insert(20, 'twenty')
tree.insert(15, 'fifteen')

console.log(tree.find(15)) // 'fifteen'
console.log(tree.size) // 3

// Remove operations
tree.remove(10)
console.log(tree.size) // 2

📚 API Reference

Constructor

new BPlusTree<T, K>(minDegree: number, unique: boolean = true, comparator?: (a: K, b: K) => number)

• T - Value type
• K - Key type (must extend ValueType: number | string | boolean)
• minDegree - Minimum degree of the B+ tree (≥ 2)
• unique - Whether to allow duplicate keys (default: true)
• comparator - Custom comparison function for keys

Basic Operations

Insert

// Insert a key-value pair
tree.insert(key: K, value: T): boolean

// Examples
tree.insert(42, { name: 'Alice', age: 30 })
tree.insert('key1', 'value1')

Find

// Find single value by key
tree.find(key: K): T | null

// Find all values for a key (useful for non-unique trees)
tree.find_all(key: K): T[]

// Examples
const user = tree.find(42)
const allUsers = tree.find_all('admin') // For duplicate keys

Remove

// Remove first occurrence of key
tree.remove(key: K): boolean

// Remove all occurrences of key
tree.remove_all(key: K): number

// Examples
tree.remove(42) // Remove first occurrence
tree.remove_all('temp') // Remove all occurrences

Utility Methods

// Get tree size (total number of key-value pairs)
tree.size: number

// Count occurrences of a specific key
tree.count(key: K): number

// Check if tree contains key
tree.contains(key: K): boolean

// Get all keys in sorted order
tree.keys(): K[]

// Get all values
tree.values(): T[]

// Get all key-value pairs
tree.entries(): [K, T][]

🔄 Transactional Operations

Basic Transaction Usage

import { TransactionContext } from 'b-pl-tree'

// Create a transaction context
const txCtx = new TransactionContext(tree)

// Perform transactional operations
tree.insert_in_transaction(10, 'ten', txCtx)
tree.insert_in_transaction(20, 'twenty', txCtx)

// Find within transaction (sees uncommitted changes)
const value = tree.get_all_in_transaction(10, txCtx) // ['ten']

// Commit the transaction
await txCtx.commit()

// Or abort the transaction
// await txCtx.abort()

Transactional API

Insert in Transaction

tree.insert_in_transaction(key: K, value: T, txCtx: TransactionContext<T, K>): boolean

Remove in Transaction

// Remove single occurrence
tree.remove_in_transaction(key: K, txCtx: TransactionContext<T, K>, all?: false): boolean

// Remove all occurrences
tree.remove_in_transaction(key: K, txCtx: TransactionContext<T, K>, all: true): boolean

Find in Transaction

tree.get_all_in_transaction(key: K, txCtx: TransactionContext<T, K>): T[]

Transaction Context Methods

// Commit transaction (apply all changes)
await txCtx.commit(): Promise<void>

// Abort transaction (discard all changes)
await txCtx.abort(): Promise<void>

// Check if transaction is active
txCtx.isActive(): boolean

🔒 Two-Phase Commit (2PC)

For distributed transactions, use the 2PC protocol:

// Phase 1: Prepare
const canCommit = await txCtx.prepareCommit()

if (canCommit) {
  // Phase 2: Finalize commit
  await txCtx.finalizeCommit()
} else {
  // Abort if prepare failed
  await txCtx.abort()
}

2PC API

// Prepare phase - validate and lock resources
txCtx.prepareCommit(): Promise<boolean>

// Finalize phase - apply changes atomically
txCtx.finalizeCommit(): Promise<void>

// Abort after prepare
txCtx.abort(): Promise<void>

💾 Savepoint Support

Savepoints provide fine-grained transaction control, allowing you to create named checkpoints within a transaction and rollback to specific points without aborting the entire transaction.

Basic Savepoint Usage

import { TransactionContext } from 'b-pl-tree'

// Create a transaction context
const txCtx = new TransactionContext(tree)

// Make some changes
tree.insert_in_transaction(10, 'ten', txCtx)
tree.insert_in_transaction(20, 'twenty', txCtx)

// Create a savepoint
const savepointId = await txCtx.createSavepoint('checkpoint-1')

// Make more changes
tree.insert_in_transaction(30, 'thirty', txCtx)
tree.remove_in_transaction(10, txCtx)

// Rollback to savepoint (reverts changes made after savepoint creation)
await txCtx.rollbackToSavepoint(savepointId)

// Now: 10='ten', 20='twenty' exist, but 30 and removal of 10 are reverted
console.log(tree.find_in_transaction(10, txCtx)) // ['ten'] - restored
console.log(tree.find_in_transaction(20, txCtx)) // ['twenty'] - remains
console.log(tree.find_in_transaction(30, txCtx)) // undefined - reverted

// Commit the transaction
await txCtx.commit()

Savepoint API

Create Savepoint

// Create a named savepoint
const savepointId = await txCtx.createSavepoint(name: string): Promise<string>

// Returns unique savepoint ID for later reference
console.log(savepointId) // "sp-tx-1234567890-abc123-1-1234567890"

Rollback to Savepoint

// Rollback to a specific savepoint
await txCtx.rollbackToSavepoint(savepointId: string): Promise<void>

// Reverts all changes made after the savepoint was created
// Automatically removes any newer savepoints

Release Savepoint

// Release a savepoint to free memory
await txCtx.releaseSavepoint(savepointId: string): Promise<void>

// Savepoint data is cleaned up, but transaction state remains unchanged

List and Inspect Savepoints

// Get list of all savepoints (sorted by name)
const savepoints = txCtx.listSavepoints(): string[]
console.log(savepoints)
// ["checkpoint-1 (sp-tx-...) - 2024-01-15T10:30:00.000Z"]

// Get detailed information about a savepoint
const info = txCtx.getSavepointInfo(savepointId: string): SavepointInfo | undefined
console.log(info)
// {
//   savepointId: "sp-tx-1234567890-abc123-1-1234567890",
//   name: "checkpoint-1",
//   timestamp: 1705315800000,
//   workingNodesCount: 2,
//   deletedNodesCount: 0
// }

Nested Savepoints

Savepoints support nesting - you can create multiple savepoints and rollback to any of them:

const txCtx = new TransactionContext(tree)

// Initial state
tree.insert_in_transaction(1, 'one', txCtx)

// First savepoint
const sp1 = await txCtx.createSavepoint('level-1')
tree.insert_in_transaction(2, 'two', txCtx)

// Second savepoint (nested)
const sp2 = await txCtx.createSavepoint('level-2')
tree.insert_in_transaction(3, 'three', txCtx)

// Third savepoint (nested deeper)
const sp3 = await txCtx.createSavepoint('level-3')
tree.insert_in_transaction(4, 'four', txCtx)

// Rollback to level-2 (removes level-3 savepoint automatically)
await txCtx.rollbackToSavepoint(sp2)

// State: 1='one', 2='two', 3='three' (4 is reverted)
// Available savepoints: level-1, level-2 (level-3 is removed)

console.log(txCtx.listSavepoints().length) // 2

Advanced Savepoint Examples

Error Recovery with Savepoints

async function complexOperation(txCtx: TransactionContext<string, number>) {
  // Create savepoint before risky operation
  const safepointId = await txCtx.createSavepoint('before-risky-operation')

  try {
    // Perform risky operations
    tree.insert_in_transaction(100, 'hundred', txCtx)
    tree.remove_in_transaction(50, txCtx) // Might fail

    // Validate results
    if (tree.find_in_transaction(100, txCtx) === undefined) {
      throw new Error('Validation failed')
    }

    // Success - release savepoint
    await txCtx.releaseSavepoint(safepointId)
    return true

  } catch (error) {
    // Error - rollback to savepoint
    console.log('Operation failed, rolling back:', error.message)
    await txCtx.rollbackToSavepoint(safepointId)
    return false
  }
}

// Usage
const txCtx = new TransactionContext(tree)
const success = await complexOperation(txCtx)

if (success) {
  await txCtx.commit()
} else {
  await txCtx.abort()
}

Batch Processing with Checkpoints

async function batchProcessWithCheckpoints(
  items: Array<[number, string]>,
  checkpointInterval: number = 100
) {
  const txCtx = new TransactionContext(tree)
  let lastCheckpoint: string | undefined

  try {
    for (let i = 0; i < items.length; i++) {
      const [key, value] = items[i]

      // Create checkpoint every N items
      if (i % checkpointInterval === 0) {
        if (lastCheckpoint) {
          await txCtx.releaseSavepoint(lastCheckpoint)
        }
        lastCheckpoint = await txCtx.createSavepoint(`checkpoint-${i}`)
      }

      // Process item
      tree.insert_in_transaction(key, value, txCtx)

      // Validate item (example)
      if (key < 0) {
        throw new Error(`Invalid key: ${key}`)
      }
    }

    // Success - commit all changes
    await txCtx.commit()
    return { success: true, processed: items.length }

  } catch (error) {
    // Error - rollback to last checkpoint
    if (lastCheckpoint) {
      console.log('Rolling back to last checkpoint')
      await txCtx.rollbackToSavepoint(lastCheckpoint)

      // Could continue processing from checkpoint or abort
      await txCtx.abort()
    } else {
      await txCtx.abort()
    }

    return { success: false, error: error.message }
  }
}

// Usage
const result = await batchProcessWithCheckpoints([
  [1, 'one'],
  [2, 'two'],
  [3, 'three']
])

Multi-Stage Transaction with Savepoints

async function multiStageTransaction() {
  const txCtx = new TransactionContext(tree)

  try {
    // Stage 1: Data preparation
    const stage1 = await txCtx.createSavepoint('stage-1-complete')
    tree.insert_in_transaction(10, 'prepared-data', txCtx)

    // Stage 2: Data transformation
    const stage2 = await txCtx.createSavepoint('stage-2-complete')
    tree.insert_in_transaction(20, 'transformed-data', txCtx)

    // Stage 3: Data validation (might fail)
    const stage3 = await txCtx.createSavepoint('stage-3-complete')
    tree.insert_in_transaction(30, 'validated-data', txCtx)

    // Simulate validation failure
    const isValid = Math.random() > 0.5
    if (!isValid) {
      // Rollback to stage 2 and try alternative approach
      await txCtx.rollbackToSavepoint(stage2)
      tree.insert_in_transaction(31, 'alternative-data', txCtx)
    }

    // Final commit
    await txCtx.commit()
    console.log('Multi-stage transaction completed successfully')

  } catch (error) {
    console.log('Transaction failed:', error.message)
    await txCtx.abort()
  }
}

Savepoint Best Practices

Memory Management

// ✅ Good: Release savepoints when no longer needed
const sp1 = await txCtx.createSavepoint('temp-checkpoint')
// ... do work ...
await txCtx.releaseSavepoint(sp1) // Free memory

// ✅ Good: Savepoints are automatically cleaned up on commit/abort
await txCtx.commit() // All savepoints are released

// ❌ Avoid: Creating too many savepoints without cleanup
for (let i = 0; i < 1000; i++) {
  await txCtx.createSavepoint(`sp-${i}`) // Memory leak!
}

Naming Conventions

// ✅ Good: Descriptive names
await txCtx.createSavepoint('before-user-validation')
await txCtx.createSavepoint('after-data-import')
await txCtx.createSavepoint('pre-calculation-phase')

// ❌ Avoid: Generic names
await txCtx.createSavepoint('sp1')
await txCtx.createSavepoint('temp')

Error Handling

// ✅ Good: Handle savepoint errors
try {
  await txCtx.rollbackToSavepoint('non-existent')
} catch (error) {
  console.log('Savepoint not found:', error.message)
  // Handle gracefully
}

// ✅ Good: Check savepoint existence
const info = txCtx.getSavepointInfo(savepointId)
if (info) {
  await txCtx.rollbackToSavepoint(savepointId)
} else {
  console.log('Savepoint no longer exists')
}

Savepoint Types and Interfaces

import { SavepointInfo, SavepointSnapshot } from 'b-pl-tree'

// Savepoint information
interface SavepointInfo {
  savepointId: string      // Unique identifier
  name: string             // User-provided name
  timestamp: number        // Creation timestamp
  workingNodesCount: number // Number of modified nodes
  deletedNodesCount: number // Number of deleted nodes
}

// Internal snapshot structure (for advanced use)
interface SavepointSnapshot<T, K> {
  savepointId: string
  name: string
  timestamp: number
  workingRootId: number | undefined
  workingNodesSnapshot: Map<number, Node<T, K>>
  deletedNodesSnapshot: Set<number>
}

📚 Complete Savepoint Example

For a comprehensive demonstration of savepoint functionality, see the complete example:

# Run the savepoint example
bun run examples/savepoint-example.ts

This example demonstrates:

• Multi-phase transactions with savepoints at each stage
• Nested savepoint management and rollback behavior
• Error recovery using savepoints as safety checkpoints
• Batch processing with checkpoint intervals
• Best practices for savepoint naming and memory management

Advanced Examples

Working with Complex Data

interface User {
  id: number
  name: string
  email: string
  age: number
}

const userTree = new BPlusTree<User, number>(3, true)

// Insert users
userTree.insert(1, { id: 1, name: 'Alice', email: '[email protected]', age: 30 })
userTree.insert(2, { id: 2, name: 'Bob', email: '[email protected]', age: 25 })

// Find user
const alice = userTree.find(1)
console.log(alice?.name) // 'Alice'

Non-Unique Index Example

// Create tree allowing duplicate keys (e.g., age index)
const ageIndex = new BPlusTree<User, number>(3, false)

// Multiple users can have the same age
ageIndex.insert(25, { id: 1, name: 'Alice', email: '[email protected]', age: 25 })
ageIndex.insert(25, { id: 2, name: 'Bob', email: '[email protected]', age: 25 })
ageIndex.insert(30, { id: 3, name: 'Charlie', email: '[email protected]', age: 30 })

// Find all users aged 25
const users25 = ageIndex.find_all(25) // Returns both Alice and Bob
console.log(users25.length) // 2

Transaction Isolation Example

// Transaction 1
const tx1 = new TransactionContext(tree)
tree.insert_in_transaction(100, 'tx1-value', tx1)

// Transaction 2 (concurrent)
const tx2 = new TransactionContext(tree)
tree.insert_in_transaction(200, 'tx2-value', tx2)

// tx1 cannot see tx2's changes and vice versa
console.log(tree.get_all_in_transaction(200, tx1)) // []
console.log(tree.get_all_in_transaction(100, tx2)) // []

// Commit tx1
await tx1.commit()

// Now main tree has tx1's changes, but tx2 still isolated
console.log(tree.find(100)) // 'tx1-value'
console.log(tree.get_all_in_transaction(100, tx2)) // [] (snapshot isolation)

// Commit tx2
await tx2.commit()
console.log(tree.find(200)) // 'tx2-value'

Batch Operations with Transactions

async function batchInsert(items: Array<[K, T]>) {
  const txCtx = new TransactionContext(tree)

  try {
    // Insert all items in transaction
    for (const [key, value] of items) {
      tree.insert_in_transaction(key, value, txCtx)
    }

    // Commit all changes atomically
    await txCtx.commit()
    return true
  } catch (error) {
    // Abort on any error
    await txCtx.abort()
    return false
  }
}

// Usage
const success = await batchInsert([
  [1, 'one'],
  [2, 'two'],
  [3, 'three']
])

💾 Serialization and Persistence

The library provides comprehensive serialization support for saving and loading B+ trees:

Adapter compatibility: Starting from 1.3.x, a resilient adapter layer normalizes (de)serialization across ESM/CJS and version differences. See Integration Guide: B_PLUS_TREE_ADAPTER.md.

Compatibility guarantees:

• Backward compatible reads of legacy payloads (stored as payload)
• New writes include adapter metadata __bpl_adapter: 'v1' and optional __bpl_version
• Fallback rebuild is O(n log n) and used only when statics are unavailable

Basic Serialization

import { serializeTree, deserializeTree, createTreeFrom } from 'b-pl-tree'

// Create and populate a tree
const tree = new BPlusTree<User, number>(3, false)
tree.insert(1, { id: 1, name: 'Alice', age: 30 })
tree.insert(2, { id: 2, name: 'Bob', age: 25 })
tree.insert(3, { id: 3, name: 'Charlie', age: 35 })

// Serialize tree to portable format
const serialized = serializeTree(tree)
console.log(serialized)
// {
//   t: 3,
//   unique: false,
//   root: 1,
//   next_node_id: 2,
//   nodes: [
//     { id: 1, leaf: true, keys: [1, 2, 3], pointers: [...], ... }
//   ]
// }

Deserialization Methods

Method 1: Deserialize into Existing Tree

// Create a new empty tree
const newTree = new BPlusTree<User, number>()

// Deserialize data into the existing tree
deserializeTree(newTree, serialized)

// Tree now contains all the original data
console.log(newTree.size) // 3
console.log(newTree.find(1)) // { id: 1, name: 'Alice', age: 30 }

Method 2: Create New Tree from Serialized Data

// Create tree directly from serialized data
const restoredTree = createTreeFrom<User, number>(serialized)

// Tree is ready to use
console.log(restoredTree.size) // 3
console.log(restoredTree.t) // 3 (from serialized data)
console.log(restoredTree.unique) // false (from serialized data)

Method 3: Create with Custom Options

// Override some options while preserving data
const customTree = createTreeFrom<User, number>(serialized, {
  t: 5,           // Will be overridden by serialized t=3
  unique: true,   // Will be overridden by serialized unique=false
  comparator: customComparator // Custom comparator will be used
})

// Serialized data takes precedence for t and unique
console.log(customTree.t) // 3 (from serialized data)
console.log(customTree.unique) // false (from serialized data)

Simple Key-Value Format

For simple use cases, you can also serialize/deserialize from plain objects:

// Simple object format
const simpleData = {
  'user1': { name: 'Alice', age: 30 },
  'user2': { name: 'Bob', age: 25 },
  'user3': { name: 'Charlie', age: 35 }
}

// Create tree from simple object
const tree = createTreeFrom<User, string>(simpleData)
console.log(tree.size) // 3

// Or deserialize into existing tree
const existingTree = new BPlusTree<User, string>()
deserializeTree(existingTree, simpleData)

File Persistence Example

import { writeFile, readFile } from 'fs/promises'

// Save tree to file
async function saveTreeToFile<T, K>(tree: BPlusTree<T, K>, filename: string): Promise<void> {
  const serialized = serializeTree(tree)
  const json = JSON.stringify(serialized, null, 2)
  await writeFile(filename, json, 'utf8')
}

// Load tree from file
async function loadTreeFromFile<T, K>(filename: string): Promise<BPlusTree<T, K>> {
  const json = await readFile(filename, 'utf8')
  const serialized = JSON.parse(json)
  return createTreeFrom<T, K>(serialized)
}

// Usage
await saveTreeToFile(userTree, 'users.json')
const loadedTree = await loadTreeFromFile<User, number>('users.json')

Database Integration Example

// Example with a database
class TreeRepository {
  async saveTree<T, K>(name: string, tree: BPlusTree<T, K>): Promise<void> {
    const serialized = serializeTree(tree)
    await db.query(
      'INSERT INTO trees (name, data) VALUES (?, ?) ON DUPLICATE KEY UPDATE data = ?',
      [name, JSON.stringify(serialized), JSON.stringify(serialized)]
    )
  }

  async loadTree<T, K>(name: string): Promise<BPlusTree<T, K> | null> {
    const result = await db.query('SELECT data FROM trees WHERE name = ?', [name])
    if (result.length === 0) return null

    const serialized = JSON.parse(result[0].data)
    return createTreeFrom<T, K>(serialized)
  }

  async restoreTreeInto<T, K>(name: string, tree: BPlusTree<T, K>): Promise<boolean> {
    const result = await db.query('SELECT data FROM trees WHERE name = ?', [name])
    if (result.length === 0) return false

    const serialized = JSON.parse(result[0].data)
    deserializeTree(tree, serialized)
    return true
  }
}

// Usage
const repo = new TreeRepository()

// Save
await repo.saveTree('user_index', userTree)

// Load
const loadedTree = await repo.loadTree<User, number>('user_index')

// Restore into existing tree
const existingTree = new BPlusTree<User, number>()
const restored = await repo.restoreTreeInto('user_index', existingTree)

Serialization API Reference

serializeTree<T, K>(tree: BPlusTree<T, K>): PortableBPlusTree<T, K>

Converts a B+ tree into a portable JSON-serializable format.

Parameters:

• tree - The B+ tree instance to serialize

Returns: Portable tree object containing:

• t - Minimum degree
• unique - Whether tree allows duplicates
• root - Root node ID
• next_node_id - Next available node ID
• nodes - Array of serialized nodes

deserializeTree<T, K>(tree: BPlusTree<T, K>, data: PortableBPlusTree<T, K> | Record<string, T>): void

Populates an existing tree with serialized data.

Parameters:

• tree - Target tree instance to populate
• data - Serialized tree data or simple key-value object

Behavior:

• Clears existing tree data
• Restores all nodes and structure
• Handles both full format and simple object format

createTreeFrom<T, K>(data: PortableBPlusTree<T, K> | Record<string, T>, options?: TreeOptions): BPlusTree<T, K>

Creates a new tree instance from serialized data.

Parameters:

• data - Serialized tree data or simple key-value object
• options - Optional tree configuration (overridden by serialized data)

Returns: New B+ tree instance with restored data

Performance Considerations

• Serialization: O(n) time complexity, where n is the number of nodes
• Deserialization: O(n) time complexity for tree reconstruction
• Memory: Serialized format is compact, typically 2-3x smaller than in-memory representation
• Large Trees: Tested with 1000+ elements, serialization/deserialization < 100ms

Error Handling

try {
  // Serialization is generally safe
  const serialized = serializeTree(tree)

  // Deserialization handles malformed data gracefully
  const newTree = createTreeFrom(serialized)
} catch (error) {
  console.error('Serialization error:', error)
  // Handle error appropriately
}

// Graceful handling of invalid data
const malformedData = { invalid: 'data' }
deserializeTree(tree, malformedData) // Won't throw, tree remains unchanged

Adapter Compatibility Layer (BPlusTreeAdapter)

To ensure stable (de)serialization across different build targets (ESM/CJS) and historical versions, the internal adapter selects the best available strategy at runtime:

• Preferred: static methods on the class (serialize, createFrom/deserialize)
• Fallbacks: constructor static, instance .serialize()
• Last resort: snapshot via each(true) iterator and rebuild by inserting items (O(n log n))

Debug logging indicates which branch was used when DEBUG_BTREE=true.

Error codes:

• BPL_ADAPTER_SERIALIZE_UNSUPPORTED
• BPL_ADAPTER_DESERIALIZE_UNSUPPORTED

Portable format adds metadata:

• __bpl_adapter: 'v1'
• Optional __bpl_version

Backward compatibility:

• Existing payloads from older serializers are preserved under payload and can be read by older consumers.

For detailed guidance and migration examples, see:

• integration/B_PLUS_TREE_ADAPTER.md

🔗 Complex Indexes and Composite Keys

Библиотека поддерживает создание сложных индексов, состоящих из нескольких полей, что позволяет создавать составные ключи для более гибкого поиска и сортировки данных.

Составные ключи с объектами

// Определяем тип составного ключа
interface CompositeKey {
  department: string
  level: number
  joinDate?: Date
}

// Создаем компаратор для составного ключа
const compositeComparator = (a: CompositeKey, b: CompositeKey): number => {
  // Обработка null/undefined значений
  if (!a || !b) {
    if (a === b) return 0
    return !a ? -1 : 1
  }

  // Сравнение по department (первый приоритет)
  if (a.department !== b.department) {
    return a.department.localeCompare(b.department)
  }

  // Сравнение по level (второй приоритет)
  if (a.level !== b.level) {
    return a.level - b.level
  }

  // Сравнение по joinDate (третий приоритет, опционально)
  if (a.joinDate && b.joinDate) {
    return a.joinDate.getTime() - b.joinDate.getTime()
  }
  if (a.joinDate && !b.joinDate) return 1
  if (!a.joinDate && b.joinDate) return -1

  return 0
}

// Создаем дерево с составным ключом
const employeeIndex = new BPlusTree<Employee, CompositeKey>(
  3,
  false, // Разрешаем дубликаты
  compositeComparator
)

Использование составных ключей

interface Employee {
  id: number
  name: string
  department: string
  level: number
  joinDate: Date
  salary: number
}

// Вставка данных с составными ключами
const employees: Employee[] = [
  {
    id: 1,
    name: 'Alice Johnson',
    department: 'Engineering',
    level: 3,
    joinDate: new Date('2020-01-15'),
    salary: 95000
  },
  {
    id: 2,
    name: 'Bob Smith',
    department: 'Engineering',
    level: 2,
    joinDate: new Date('2021-03-10'),
    salary: 75000
  },
  {
    id: 3,
    name: 'Charlie Brown',
    department: 'Marketing',
    level: 3,
    joinDate: new Date('2019-08-22'),
    salary: 85000
  }
]

// Индексирование по составному ключу
employees.forEach(emp => {
  const compositeKey: CompositeKey = {
    department: emp.department,
    level: emp.level,
    joinDate: emp.joinDate
  }
  employeeIndex.insert(compositeKey, emp)
})

// Поиск по точному составному ключу
const engineeringLevel3 = employeeIndex.find_all({
  department: 'Engineering',
  level: 3
})

// Поиск с частичным ключом (используя query API)
import { sourceEach, filter, executeQuery } from 'b-pl-tree'

const engineeringEmployees = executeQuery(
  sourceEach<Employee, CompositeKey>(true),
  filter(([key, _]) => key.department === 'Engineering')
)(employeeIndex)

Массивы как составные ключи

// Использование массивов для составных ключей
import { compare_keys_array } from 'b-pl-tree'

// Составной ключ: [год, месяц, день, час]
type DateTimeKey = [number, number, number, number]

const timeSeriesIndex = new BPlusTree<SensorReading, DateTimeKey>(
  3,
  false,
  compare_keys_array // Встроенный компаратор для массивов
)

interface SensorReading {
  sensorId: string
  value: number
  timestamp: Date
}

// Вставка данных временных рядов
const readings: SensorReading[] = [
  {
    sensorId: 'temp-01',
    value: 23.5,
    timestamp: new Date('2024-01-15T10:30:00')
  },
  {
    sensorId: 'temp-02',
    value: 24.1,
    timestamp: new Date('2024-01-15T10:31:00')
  }
]

readings.forEach(reading => {
  const date = reading.timestamp
  const key: DateTimeKey = [
    date.getFullYear(),
    date.getMonth() + 1,
    date.getDate(),
    date.getHours()
  ]
  timeSeriesIndex.insert(key, reading)
})

// Поиск данных за конкретный час
const hourlyData = timeSeriesIndex.find_all([2024, 1, 15, 10])

Многоуровневые индексы

// Создание системы многоуровневых индексов
class EmployeeDatabase {
  // Первичный индекс по ID
  private primaryIndex = new BPlusTree<Employee, number>(3, true)

  // Вторичный индекс по отделу и уровню
  private departmentLevelIndex = new BPlusTree<Employee, CompositeKey>(
    3,
    false,
    compositeComparator
  )

  // Индекс по зарплате (для диапазонных запросов)
  private salaryIndex = new BPlusTree<Employee, number>(3, false)

  addEmployee(employee: Employee): void {
    // Вставка в первичный индекс
    this.primaryIndex.insert(employee.id, employee)

    // Вставка во вторичные индексы
    this.departmentLevelIndex.insert({
      department: employee.department,
      level: employee.level,
      joinDate: employee.joinDate
    }, employee)

    this.salaryIndex.insert(employee.salary, employee)
  }

  // Поиск по ID (быстрый поиск)
  findById(id: number): Employee | null {
    return this.primaryIndex.find(id)
  }

  // Поиск по отделу и уровню
  findByDepartmentAndLevel(department: string, level: number): Employee[] {
    return this.departmentLevelIndex.find_all({
      department,
      level
    })
  }

  // Поиск в диапазоне зарплат
  findBySalaryRange(minSalary: number, maxSalary: number): Employee[] {
    const results: Employee[] = []

    // Используем query API для диапазонного поиска
    const generator = executeQuery(
      sourceRange<Employee, number>(minSalary, maxSalary, true, true),
      filter(([salary, _]) => salary >= minSalary && salary <= maxSalary)
    )(this.salaryIndex)

    for (const cursor of generator) {
      results.push(cursor.value)
    }

    return results
  }
}

Транзакционная поддержка для сложных индексов

// Транзакционные операции с несколькими индексами
async function addEmployeeTransactionally(
  database: EmployeeDatabase,
  employee: Employee
): Promise<boolean> {
  const primaryTx = database.primaryIndex.begin_transaction()
  const departmentTx = database.departmentLevelIndex.begin_transaction()
  const salaryTx = database.salaryIndex.begin_transaction()

  try {
    // Вставка во все индексы в рамках транзакций
    database.primaryIndex.insert_in_transaction(employee.id, employee, primaryTx)

    database.departmentLevelIndex.insert_in_transaction({
      department: employee.department,
      level: employee.level,
      joinDate: employee.joinDate
    }, employee, departmentTx)

    database.salaryIndex.insert_in_transaction(employee.salary, employee, salaryTx)

    // Подготовка к коммиту (2PC)
    const canCommit = await Promise.all([
      primaryTx.prepareCommit(),
      departmentTx.prepareCommit(),
      salaryTx.prepareCommit()
    ])

    if (canCommit.every(result => result)) {
      // Финализация коммита
      await Promise.all([
        primaryTx.finalizeCommit(),
        departmentTx.finalizeCommit(),
        salaryTx.finalizeCommit()
      ])
      return true
    } else {
      throw new Error('Prepare phase failed')
    }
  } catch (error) {
    // Откат всех транзакций
    await Promise.all([
      primaryTx.abort(),
      departmentTx.abort(),
      salaryTx.abort()
    ])
    return false
  }
}

Встроенные компараторы

Библиотека предоставляет готовые компараторы для различных типов составных ключей. Компараторы не являются обязательными - если не указать компаратор, будет использован стандартный компаратор для примитивных типов.

1. Компаратор для примитивных типов

import { compare_keys_primitive } from 'b-pl-tree'

// Автоматически используется по умолчанию для number, string, boolean
const simpleTree = new BPlusTree<User, number>(3, true)
// Эквивалентно:
const explicitTree = new BPlusTree<User, number>(3, true, compare_keys_primitive)

// Поддерживает сравнение:
// - Чисел: 1 < 2 < 3
// - Строк: 'a' < 'b' < 'c' (лексикографическое сравнение)
// - Булевых значений: false < true
// - Смешанных типов с приоритетом: boolean < number < string

2. Компаратор для массивов

import { compare_keys_array } from 'b-pl-tree'

// Сравнивает массивы поэлементно
const arrayTree = new BPlusTree<Data, number[]>(3, false, compare_keys_array)

// Примеры сравнения:
// [1, 2] < [1, 3]     (второй элемент больше)
// [1, 2] < [1, 2, 3]  (первый массив короче)
// [2] > [1, 9, 9]     (первый элемент больше)

// Практическое применение - временные ряды
type TimeKey = [year: number, month: number, day: number, hour: number]
const timeSeriesTree = new BPlusTree<SensorData, TimeKey>(3, false, compare_keys_array)

// Автоматическая сортировка по времени:
timeSeriesTree.insert([2024, 1, 15, 10], data1)  // 2024-01-15 10:00
timeSeriesTree.insert([2024, 1, 15, 9], data2)   // 2024-01-15 09:00
timeSeriesTree.insert([2024, 1, 16, 8], data3)   // 2024-01-16 08:00

3. Компаратор для объектов

import { compare_keys_object } from 'b-pl-tree'

// Сравнивает объекты по всем свойствам в алфавитном порядке ключей
interface ProductKey {
  category: string
  brand: string
  price: number
}

const productTree = new BPlusTree<Product, ProductKey>(
  3,
  false,
  compare_keys_object
)

// Порядок сравнения: brand -> category -> price (алфавитный порядок ключей)
// Примеры:
// { brand: 'Apple', category: 'Electronics', price: 999 }
// < { brand: 'Apple', category: 'Electronics', price: 1099 }
// < { brand: 'Samsung', category: 'Electronics', price: 899 }

// ВАЖНО: Все объекты должны иметь одинаковую структуру ключей

4. Создание пользовательских компараторов

Для более сложной логики сравнения создавайте собственные компараторы:

Смешанный порядок сортировки (ASC/DESC)

// Пример: сортировка по отделу (по возрастанию), затем по зарплате (по убыванию)
interface EmployeeSortKey {
  department: string  // ASC
  salary: number      // DESC
  joinDate: Date      // ASC
}

const mixedSortComparator = (a: EmployeeSortKey, b: EmployeeSortKey): number => {
  // 1. Отдел по возрастанию (A-Z)
  if (a.department !== b.department) {
    return a.department.localeCompare(b.department) // ASC
  }

  // 2. Зарплата по убыванию (высокая -> низкая)
  if (a.salary !== b.salary) {
    return b.salary - a.salary // DESC (обратный порядок)
  }

  // 3. Дата приема по возрастанию (старые -> новые)
  return a.joinDate.getTime() - b.joinDate.getTime() // ASC
}

// Результат сортировки:
// Engineering, $100000, 2020-01-01
// Engineering, $95000,  2021-01-01
// Engineering, $90000,  2019-01-01
// Marketing,   $85000,  2020-06-01
// Marketing,   $80000,  2021-03-01

Приоритетная сортировка с весами

// Пример: система рейтингов с приоритетами
interface RatingKey {
  priority: number    // DESC (высокий приоритет первым)
  score: number       // DESC (высокий балл первым)
  timestamp: Date     // ASC (старые записи первыми при равенстве)
}

const priorityComparator = (a: RatingKey, b: RatingKey): number => {
  // 1. Приоритет по убыванию (1 = высший, 5 = низший)
  if (a.priority !== b.priority) {
    return a.priority - b.priority // ASC для приоритета (1, 2, 3, 4, 5)
  }

  // 2. Балл по убыванию (100 -> 0)
  if (a.score !== b.score) {
    return b.score - a.score // DESC
  }

  // 3. Время по возрастанию (FIFO при равенстве)
  return a.timestamp.getTime() - b.timestamp.getTime() // ASC
}

Географическая сортировка

// Пример: сортировка локаций
interface LocationKey {
  country: string     // ASC (алфавитный порядок)
  population: number  // DESC (большие города первыми)
  name: string        // ASC (алфавитный порядок городов)
}

const geoComparator = (a: LocationKey, b: LocationKey): number => {
  // 1. Страна по алфавиту
  if (a.country !== b.country) {
    return a.country.localeCompare(b.country)
  }

  // 2. Население по убыванию (мегаполисы первыми)
  if (a.population !== b.population) {
    return b.population - a.population
  }

  // 3. Название города по алфавиту
  return a.name.localeCompare(b.name)
}

// Результат:
// Russia, Moscow, 12000000
// Russia, SPb, 5000000
// Russia, Kazan, 1200000
// USA, NYC, 8000000
// USA, LA, 4000000

Версионная сортировка

// Пример: сортировка версий ПО
interface VersionKey {
  major: number       // DESC (новые версии первыми)
  minor: number       // DESC
  patch: number       // DESC
  isStable: boolean   // DESC (стабильные версии первыми)
}

const versionComparator = (a: VersionKey, b: VersionKey): number => {
  // 1. Стабильность (true > false)
  if (a.isStable !== b.isStable) {
    return b.isStable ? 1 : -1 // Стабильные первыми
  }

  // 2. Major версия по убыванию
  if (a.major !== b.major) {
    return b.major - a.major
  }

  // 3. Minor версия по убыванию
  if (a.minor !== b.minor) {
    return b.minor - a.minor
  }

  // 4. Patch версия по убыванию
  return b.patch - a.patch
}

// Результат:
// 2.1.0 (stable)
// 2.0.5 (stable)
// 2.0.0 (stable)
// 2.2.0 (beta)
// 2.1.1 (beta)

// Компаратор с приоритетами полей
interface EmployeeKey {
  department: string
  level: number
  joinDate: Date
}

const employeeComparator = (a: EmployeeKey, b: EmployeeKey): number => {
  // Приоритет 1: Отдел
  if (a.department !== b.department) {
    return a.department.localeCompare(b.department)
  }

  // Приоритет 2: Уровень (по убыванию)
  if (a.level !== b.level) {
    return b.level - a.level // Обратный порядок
  }

  // Приоритет 3: Дата приема на работу
  return a.joinDate.getTime() - b.joinDate.getTime()
}

// Компаратор с обработкой null/undefined
const nullSafeComparator = (a: string | null, b: string | null): number => {
  if (a === null && b === null) return 0
  if (a === null) return -1  // null считается меньше
  if (b === null) return 1
  return a.localeCompare(b)
}

// Компаратор для сложных вложенных структур
interface LocationKey {
  country: string
  city: string
  coordinates: { lat: number; lng: number }
}

const locationComparator = (a: LocationKey, b: LocationKey): number => {
  // Сначала по стране
  if (a.country !== b.country) {
    return a.country.localeCompare(b.country)
  }

  // Затем по городу
  if (a.city !== b.city) {
    return a.city.localeCompare(b.city)
  }

  // Наконец по координатам (сначала широта, потом долгота)
  if (a.coordinates.lat !== b.coordinates.lat) {
    return a.coordinates.lat - b.coordinates.lat
  }

  return a.coordinates.lng - b.coordinates.lng
}

5. Производительность компараторов

// Оптимизированный компаратор для частых сравнений
const optimizedComparator = (a: ComplexKey, b: ComplexKey): number => {
  // Быстрое сравнение наиболее различающихся полей в первую очередь

  // 1. Числовые поля сравниваются быстрее строковых
  if (a.numericField !== b.numericField) {
    return a.numericField - b.numericField
  }

  // 2. Короткие строки сравниваются быстрее длинных
  if (a.shortString !== b.shortString) {
    return a.shortString.localeCompare(b.shortString)
  }

  // 3. Дорогие операции в последнюю очередь
  return a.expensiveField.localeCompare(b.expensiveField)
}

// Кэширование результатов для очень дорогих компараторов
const memoizedComparator = (() => {
  const cache = new Map<string, number>()

  return (a: ComplexKey, b: ComplexKey): number => {
    const cacheKey = `${JSON.stringify(a)}_${JSON.stringify(b)}`

    if (cache.has(cacheKey)) {
      return cache.get(cacheKey)!
    }

    const result = expensiveComparisonLogic(a, b)
    cache.set(cacheKey, result)
    return result
  }
})()

6. Рекомендации по выбору компараторов

• Простые ключи (number, string, boolean): Используйте стандартный компаратор (не указывайте)
• Массивы: Используйте compare_keys_array для временных рядов, координат, версий
• Объекты с одинаковой структурой: Используйте compare_keys_object
• Сложная логика: Создавайте пользовательские компараторы
• Производительность критична: Оптимизируйте порядок сравнения полей
• Null/undefined значения: Обрабатывайте явно в пользовательских компараторах

Примеры смешанной сортировки (ASC/DESC)

Для демонстрации различных типов смешанной сортировки создан специальный пример:

# Запуск примера смешанной сортировки
bun run examples/mixed-sort-example.ts

Этот пример демонстрирует:

• Рейтинг сотрудников: отдел (ASC), зарплата (DESC), дата приема (ASC)
• Каталог товаров: категория (ASC), в наличии (DESC), рейтинг (DESC), цена (ASC)
• Планирование событий: приоритет (custom), срочность (DESC), время (ASC)
• Управление версиями: стабильность (DESC), major (DESC), minor (DESC), patch (DESC)

📖 Подробное руководство: Для детального изучения смешанной сортировки см. MIXED_SORT_GUIDE.md

Практические применения составных ключей

1. Системы управления базами данных

// Индекс для таблицы заказов: (customer_id, order_date, order_id)
interface OrderKey {
  customerId: number
  orderDate: Date
  orderId: number
}

const orderComparator = (a: OrderKey, b: OrderKey): number => {
  if (a.customerId !== b.customerId) return a.customerId - b.customerId
  if (a.orderDate.getTime() !== b.orderDate.getTime()) {
    return a.orderDate.getTime() - b.orderDate.getTime()
  }
  return a.orderId - b.orderId
}

// Эффективные запросы:
// - Все заказы клиента
// - Заказы клиента за период
// - Конкретный заказ

2. Геопространственные индексы

// Индекс для геолокации: (страна, регион, город, почтовый_код)
type GeoKey = [country: string, region: string, city: string, postalCode: string]

const geoIndex = new BPlusTree<Location, GeoKey>(3, false, compare_keys_array)

// Быстрый поиск по иерархии:
// - Все локации в стране
// - Все города в регионе
// - Точный адрес

3. Временные ряды и аналитика

// Метрики по времени: (метрика, год, месяц, день, час)
type MetricKey = [metric: string, year: number, month: number, day: number, hour: number]

const metricsIndex = new BPlusTree<MetricData, MetricKey>(3, false, compare_keys_array)

// Агрегация данных:
// - Все метрики за день
// - Конкретная метрика за период
// - Почасовая детализация

4. Многоуровневые каталоги

// Каталог товаров: (категория, подкатегория, бренд, модель)
interface ProductCatalogKey {
  category: string
  subcategory: string
  brand: string
  model: string
}

// Навигация по каталогу:
// - Все товары категории
// - Товары бренда в подкатегории
// - Конкретная модель

5. Системы версионирования

// Версии документов: (проект, документ, версия_мажор, версия_минор)
type VersionKey = [project: string, document: string, major: number, minor: number]

const versionIndex = new BPlusTree<DocumentVersion, VersionKey>(3, false, compare_keys_array)

// Управление версиями:
// - Все версии документа
// - Последняя версия проекта
// - Конкретная версия

Производительность сложных индексов

• Время поиска: O(log n) для любого типа составного ключа
• Память: Минимальные накладные расходы благодаря эффективному хранению
• Транзакции: Copy-on-Write обеспечивает изоляцию без блокировок
• Масштабируемость: Поддержка миллионов записей с составными ключами

Рекомендации по проектированию составных ключей

Порядок полей в ключе

// ❌ Неэффективный порядок (редко используемое поле первым)
interface BadKey {
  timestamp: Date    // Уникальное значение
  category: string   // Часто используется в запросах
  userId: number     // Часто используется в запросах
}

// ✅ Эффективный порядок (часто используемые поля первыми)
interface GoodKey {
  category: string   // Часто используется в запросах
  userId: number     // Часто используется в запросах
  timestamp: Date    // Уникальное значение для сортировки
}

Селективность полей

// Располагайте поля по убыванию селективности
interface OptimalKey {
  highSelectivity: string    // Много уникальных значений
  mediumSelectivity: number  // Средняя селективность
  lowSelectivity: boolean    // Мало уникальных значений
}

Размер ключей

// ❌ Слишком большие ключи
interface HeavyKey {
  longDescription: string  // Может быть очень длинным
  metadata: object        // Сложная структура
}

// ✅ Компактные ключи
interface LightKey {
  id: number             // Компактный идентификатор
  type: string           // Короткая строка
  priority: number       // Числовое значение
}

🧪 Query Operations

The library includes powerful query capabilities:

import { query, map, filter, reduce } from 'b-pl-tree'

// Complex query example
const result = await query(
  tree.includes([1, 3, 5]), // Get specific keys
  filter(([key, value]) => value.age > 20), // Filter by condition
  map(([key, value]) => ({ ...value, key })), // Transform data
  reduce((acc, item) => {
    acc.set(item.name, item)
    return acc
  }, new Map()) // Reduce to final result
)(tree)

⚡ Performance Characteristics

Benchmarks & coverage:

• Run tests with coverage: bun x vitest run --coverage

• Dev benchmarks: bun run dev/benchmarks.js (see dev/ folder for more)

• Time Complexity:

  • Insert: O(log n)
  • Find: O(log n)
  • Remove: O(log n)
  • Range queries: O(log n + k) where k is result size

• Space Complexity: O(n)

• Transaction Overhead: Minimal with Copy-on-Write optimization

🛡️ Type Safety

Full TypeScript support with generic types:

// Strongly typed tree
const stringTree = new BPlusTree<string, number>(3)
stringTree.insert(1, "hello") // ✅ Valid
stringTree.insert("1", "hello") // ❌ Type error

// Custom key types
const dateTree = new BPlusTree<Event, string>(3, true, (a, b) => a.localeCompare(b))

🔧 Configuration Options

Custom Comparator

// Custom string comparator (case-insensitive)
const tree = new BPlusTree<string, string>(3, true, (a, b) =>
  a.toLowerCase().localeCompare(b.toLowerCase())
)

// Date comparator
const dateTree = new BPlusTree<Event, Date>(3, true, (a, b) =>
  a.getTime() - b.getTime()
)

Tree Parameters

• Minimum Degree (t): Controls node size

  • Larger values = fewer levels, more memory per node
  • Smaller values = more levels, less memory per node
  • Recommended: 3-10 for most use cases

• Unique vs Non-Unique:

  • unique: true - Primary index behavior
  • unique: false - Secondary index behavior

🧪 Debugging & Error Handling

• Enable adapter debug logs:

  • DEBUG_BTREE=true — shows the selected adapter branch (static/ctor/instance/fallback)
  • VERBOSE_BTREE=true — extra verbosity for performance and internal details

• Error codes:

  • BPL_ADAPTER_SERIALIZE_UNSUPPORTED — no supported serialization strategy found
  • BPL_ADAPTER_DESERIALIZE_UNSUPPORTED — no supported deserialization strategy/snapshot

try {
  const txCtx = new TransactionContext(tree)

  // Transactional operations
  tree.insert_in_transaction(key, value, txCtx)

  // Commit with error handling
  await txCtx.commit()
} catch (error) {
  console.error('Transaction failed:', error)
  // Transaction is automatically aborted on error
}

📊 Monitoring and Debugging

// Tree statistics
console.log(`Tree size: ${tree.size}`)
console.log(`Tree height: ${tree.height}`)
console.log(`Node count: ${tree.nodeCount}`)

// Debug tree structure
tree.printTree() // Prints tree structure to console

// Validate tree integrity
const isValid = tree.validate()
console.log(`Tree is valid: ${isValid}`)

❓ FAQ

• Почему вижу “BPlusTree.serialize is not a function”? Вероятно, у вас смешанный ESM/CJS импорт или отличается версия экспортов. Используйте serializeTree/deserializeTree — адаптер выберет корректную стратегию.

• Стало медленно при восстановлении? Проверьте логи с DEBUG_BTREE=true. Если используется fallback‑rebuild — убедитесь, что доступен статический createFrom/deserialize или используйте актуальную версию библиотеки.

• Можно ли читать старые JSON‑дампы? Да. Поле payload поддерживается, при записи добавляются метаданные адаптера.

• Где посмотреть детали по адаптеру? См. integration/B_PLUS_TREE_ADAPTER.md.

🤝 Contributing

1. Fork the repository
2. Create your feature branch (git checkout -b feature/amazing-feature)
3. Run tests (bun test)
4. Commit your changes (git commit -m 'Add amazing feature')
5. Push to the branch (git push origin feature/amazing-feature)
6. Open a Pull Request

📄 License

This project is licensed under the MIT License - see the LICENSE file for details.

🙏 Acknowledgments

• Inspired by classical B+ tree algorithms
• Built with modern TypeScript best practices
• Comprehensive test suite ensuring reliability

📊 Status: Production Ready 🧪 Tests: 373/373 Passing 🔧 TypeScript: Full Support 📦 Dependencies: Zero