serializable-bptree

This is a B+tree that's totally okay with duplicate values. If you need to keep track of the B+ tree's state, don't just leave it in memory - make sure you write it down.

import { readFileSync, writeFileSync, unlinkSync, existsSync } from 'fs'
import {
  BPTreeSync,
  SerializeStrategySync,
  NumericComparator
} from 'serializable-bptree'

class FileStoreStrategySync extends SerializeStrategySync<K, V> {
  id(): string {
    return crypto.randomUUID()
  }

  read(id: string): BPTreeNode<K, V> {
    const raw = readFileSync(id, 'utf8')
    return JSON.parse(raw)
  }

  write(id: string, node: BPTreeNode<K, V>): void {
    const stringify = JSON.stringify(node)
    writeFileSync(id, stringify, 'utf8')
  }

  delete(id: string): void {
    unlinkSync(id)
  }

  readHead(): SerializeStrategyHead|null {
    if (!existsSync('head')) {
      return null
    }
    const raw = readFileSync('head', 'utf8')
    return JSON.parse(raw)
  }

  writeHead(head: SerializeStrategyHead): void {
    const stringify = JSON.stringify(head)
    writeFileSync('head', stringify, 'utf8')
  }
}

const order = 5
const tree = new BPTreeSync(
  new FileStoreStrategySync(order),
  new NumericComparator()
)

tree.init()
tree.insert('a', 1)
tree.insert('b', 2)
tree.insert('c', 3)

tree.delete('b', 2)

tree.where({ equal: 1 }) // Map([{ key: 'a', value: 1 }])
tree.where({ gt: 1 }) // Map([{ key: 'c', value: 3 }])
tree.where({ lt: 2 }) // Map([{ key: 'a', value: 1 }])
tree.where({ gt: 0, lt: 4 }) // Map([{ key: 'a', value: 1 }, { key: 'c', value: 3 }])
tree.where({ or: [3, 1] }) // Map([{ key: 'a', value: 1 }, { key: 'c', value: 3 }])
tree.where({ like: 'user_%' }) // Matches values matching the pattern

tree.clear()

Why use a serializable-bptree?

Firstly, in most cases, there is no need to use a B+tree in JavaScript. This is because there is a great alternative, the Map object. Nonetheless, if you need to retrieve values in a sorted order, a B+tree can be a good solution. These cases are often related to databases, and you may want to store this state not just in memory, but on a remote server or in a file. In this case, serializable-bptree can help you.

Additionally, this library supports asynchronous operations and rule-based query optimization for multi-index scenarios. Please refer to the sections below for more details.

Key Features

• Transactions: Supports ACID transactions with Snapshot Isolation (MVCC).
• Serializable: Save and load the B+Tree state to/from any storage (File, DB, Memory, etc.).
• Duplicate Values: Naturally handles duplicate values.
• Async/Sync Support: Provides both synchronous and asynchronous APIs.
• Query Optimization: Rule-based optimizer to choose the best index for complex queries.
• TypeScript: Fully typed for a better developer experience.

How to use

Node.js (cjs)

npm i serializable-bptree

import {
  BPTreeSync,
  BPTreeAsync,
  SerializeStrategySync,
  SerializeStrategyAsync,
  NumericComparator,
  StringComparator
} from 'serializable-bptree'

Browser (esm)

<script type="module">
  import {
    BPTreeSync,
    BPTreeAsync,
    InMemoryStoreStrategySync,
    InMemoryStoreStrategyAsync,
    ValueComparator,
    NumericComparator,
    StringComparator
  } from 'https://cdn.jsdelivr.net/npm/serializable-bptree@8/+esm'
</script>

Documentation

Explore the detailed guides and concepts of serializable-bptree:

• Core Concepts
  • Value Comparators: How sorting and matching works.
  • Serialize Strategies: How to persist nodes to storage.
• API & Usage
  • Query Conditions: Detailed explanation of the where() operators.
  • Asynchronous Usage: How to use the tree in an async environment.
• Advanced Topics
  • Transaction System (MVCC): ACID transactions, Snapshot Isolation, and Optimistic Locking.
  • Best Practices: Tips for bulk insertion and performance optimization.
  • Duplicate Value Handling: Strategies for managing large amounts of duplicate data.
  • Concurrency & Synchronization: Multi-instance usage and locking mechanisms.
  • Query Optimization Guide: How to use ChooseDriver and keys() for complex queries.

Quick Example: Query Optimization

When you have multiple indexes (e.g., an index for id and another for age), you can use ChooseDriver to select the most efficient index for your query.

const query = { id: { equal: 100 }, age: { gt: 20 } }

// 1. Select the best index based on condition priority
const candidates = [
  { tree: idxId, condition: query.id },
  { tree: idxAge, condition: query.age }
]
const driver = BPTreeSync.ChooseDriver(candidates)
const others = candidates.filter((c) => driver.tree !== c.tree)

// 2. Execute query using the selected driver
let keys = driver.tree.keys(driver.condition)
for (const { tree, condition } of others) {
  keys = tree.keys(condition, keys)
}

console.log('Found: ', keys)

Migration

Instructions for migrating between major versions (e.g., v8.0.0, v6.0.0) can be found in the Migration Guide.

LICENSE

MIT LICENSE