High-performance B+ Tree data structure implementation in TypeScript with visualization support
npm install @prachwal_org/bplus-tree

A high-performance B+ Tree data structure implementation in TypeScript with comprehensive visualization support and pluggable storage providers.
- ๐ High Performance: Optimized B+ Tree implementation with configurable capacity
- ๐ Type Safety: Full TypeScript support with generics
- ๐ Visualization: ASCII tree printing and Mermaid diagram generation
- ๐พ Persistence: Pluggable storage providers (File, Redis, and more)
- ๐งช Well Tested: 93%+ test coverage with performance benchmarks
- ๐ฆ ES Modules: Modern JavaScript module support
- ๐ง Scalable: Handles 100k+ elements efficiently
``bash`
npm install @prachwal_org/bplus-tree
`typescript
import { BPlusTree } from '@prachwal_org/bplus-tree';
// Create a new B+ Tree
const tree = new BPlusTree
// Insert values
tree.insert(10, 'value1');
tree.insert(20, 'value2');
tree.insert(5, 'value3');
// Lookup values
console.log(tree.lookup(10)); // 'value1'
console.log(tree.lookup(15)); // null
// Get all keys
console.log(tree.getAllKeys()); // [5, 10, 20]
// Visualize the tree
console.log(tree.generateMermaid()); // Generate Mermaid diagram
tree.printAsciiTree(); // Print ASCII tree
tree.saveMermaidToFile('tree.md'); // Save diagram to file
`
BPlusTree supports pluggable storage providers for persistence. The library includes built-in providers and allows custom implementations.
#### File Storage
`typescript
import { BPlusTree } from '@prachwal_org/bplus-tree';
import { FileStorageProvider } from '@prachwal_org/bplus-tree';
const tree = new BPlusTree
const provider = new FileStorageProvider('tree-data.msgpack');
// Insert data
tree.insert(1, 'value1');
tree.insert(2, 'value2');
// Save to file
await tree.save(provider);
// Load from file
await tree.load(provider);
`
#### Redis Storage
`typescript
import { BPlusTree } from '@prachwal_org/bplus-tree';
import { RedisStorageProvider } from '@prachwal_org/bplus-tree';
const tree = new BPlusTree
const provider = new RedisStorageProvider('my-tree-data');
// Connect to Redis
await provider.connect();
// Save/Load operations
await tree.save(provider);
await tree.load(provider);
// Cleanup
await provider.disconnect();
`
Implement the StorageProvider interface for custom storage backends:
`typescript
import { StorageProvider } from '@prachwal_org/bplus-tree';
class MyCustomProvider implements StorageProvider {
async save(data: Buffer): Promise
// Your save logic here
}
async load(): Promise
// Your load logic here
}
}
`
See PROVIDERS_PLAN.md for a comprehensive list of planned storage providers.
#### Constructor
`typescript`
new BPlusTree
#### Methods
##### insert(key: number, value: T): void
Inserts a key-value pair into the tree.
##### lookup(key: number): T | null
Retrieves the value associated with the given key.
##### getAllKeys(): number[]
Returns all keys in the tree in sorted order.
##### generateMermaid(): string
Generates a Mermaid diagram representing the tree structure.
##### printAsciiTree(): void
Prints an ASCII representation of the tree to the console.
##### saveMermaidToFile(filename?: string): void
Saves a Mermaid diagram to a Markdown file.
##### save(provider: StorageProvider): Promise
Saves the tree to a storage provider.
##### load(provider: StorageProvider): Promise
Loads the tree from a storage provider.
`typescript
interface User {
name: string;
age: number;
data: number[];
}
const tree = new BPlusTree
tree.insert(1, {
name: 'Alice',
age: 30,
data: [1, 2, 3]
});
tree.insert(2, {
name: 'Bob',
age: 25,
data: [4, 5, 6]
});
`
`typescript
const tree = new BPlusTree
// Add some data
for (let i = 1; i <= 10; i++) {
tree.insert(i, value${i});
}
// Generate Mermaid diagram
const mermaid = tree.generateMermaid();
console.log(mermaid);
// Save to file
tree.saveMermaidToFile('my-tree.md');
`
`bashInstall dependencies
npm install
Algorithm Details
This implementation uses a B+ Tree with the following characteristics:
- Order: Configurable capacity (default: 100)
- Leaf Level: All data is stored in leaf nodes
- Internal Nodes: Contain only keys and child pointers
- Balanced: All leaf nodes are at the same level
- Sorted: Keys are maintained in sorted order
Performance
- Insert: O(log n)
- Lookup: O(log n)
- Range Queries: O(log n + k) where k is the number of results
Contributing
1. Fork the repository
2. Create your feature branch (
git checkout -b feature/amazing-feature)
3. Commit your changes (git commit -m 'Add some amazing feature')
4. Push to the branch (git push origin feature/amazing-feature`)This project is licensed under the MIT License - see the LICENSE file for details.
If you find this project helpful, please give it a โญ๏ธ!
For issues and questions, please open an issue on GitHub.