bplus-index 0.1.0

# bplus-index

Arena-backed B+Tree for in-memory sorted indexes in Rust.

Designed for data-oriented architectures where you need secondary indexes on
tables backed by slotmaps or ECS-style storage. Supports non-unique keys
natively -- the `(K, V)` pair is the unique identity of each entry.

## Features

- **Arena storage** -- all nodes live in contiguous `Vec`s indexed by `u32`. No
  `Box`, no heap allocation per node, no pointer chasing between siblings.
- **Cache-friendly** -- each leaf holds up to 64 entries in inline `ArrayVec`s.
  Range scans follow a doubly-linked leaf chain with sequential memory access.
- **Non-unique keys** -- first-class support for one-to-many and many-to-many
  secondary indexes. Inner node separators store `(K, V)` for correct routing.
- **Zero `unsafe`** -- built on `arrayvec`. No raw pointer manipulation.
- **Minimal API** -- `insert`, `delete`, `update`, `lookup_unique`,
  `lookup_range`, `range`, `iter`. One struct covers unique, 1:N, and N:N
  indexes depending on the choice of K and V.

## Complexity

| Operation        | Time         |
|------------------|--------------|
| `insert`         | O(log n)     |
| `delete`         | O(log n)     |
| `update`         | O(log n)     |
| `lookup_unique`  | O(log n)     |
| `lookup_range`   | O(log n + k) |
| `range`          | O(log n + k) |
| `iter`           | O(n)         |

Where n is the total number of entries and k is the number of results.

## Usage

```toml
[dependencies]
bplus-index = "0.1"
```

### Unique index

```rust
use bplus_index::BPlusIndex;

let mut idx = BPlusIndex::<u64, u32>::new();
idx.insert(42, 1001); // key=42, row_id=1001

assert_eq!(idx.lookup_unique(&42), Some(&1001));
```

### Non-unique 1:N index

```rust
use bplus_index::BPlusIndex;

// One score -> many player ids
let mut idx = BPlusIndex::<i32, u64>::new();
idx.insert(1500, 1);
idx.insert(1500, 2);
idx.insert(1500, 3);

let players: Vec<_> = idx.lookup_range(&1500).copied().collect();
assert_eq!(players, vec![1, 2, 3]);
```

### Composite key for N:N index

```rust
use bplus_index::BPlusIndex;

// (game_mode, mmr) -> ticket_id
let mut idx = BPlusIndex::<(u8, i32), u64>::new();
idx.insert((1, 1200), 100);
idx.insert((1, 1350), 101);
idx.insert((1, 1400), 102);
idx.insert((2, 1300), 103);

// Range scan: mode 1, mmr 1200..1400
let tickets: Vec<_> = idx.range((1, 1200)..(1, 1400))
    .map(|(_, id)| *id)
    .collect();
assert_eq!(tickets, vec![100, 101]);
```

### Update (re-index)

```rust
use bplus_index::BPlusIndex;

let mut idx = BPlusIndex::<i32, u64>::new();
idx.insert(1500, 42);

// Player 42's score changed from 1500 to 1600
idx.update(&1500, 1600, 42);

assert_eq!(idx.lookup_unique(&1500), None);
assert_eq!(idx.lookup_unique(&1600), Some(&42));
```

## Benchmarks

Run benchmarks against `std::collections::BTreeMap`:

```sh
cargo bench
```

## Design notes

### Why not `BTreeMap`?

`BTreeMap` is a B-Tree (not B+Tree) -- values are stored in both leaf and
internal nodes, and there is no leaf chain. Range scans require climbing back
up the tree to visit the next subtree. Each node is a separate heap allocation,
so sibling traversal involves pointer chasing.

`BPlusIndex` stores values only in leaves, which are linked for O(1) sibling
traversal. Nodes live in flat `Vec`s for better memory locality.

### Why `(K, V)` separators in inner nodes?

Standard B+Trees use K-only separators, which breaks down when the same key
appears in multiple leaves. A query for key K would descend into one subtree
and miss entries in adjacent subtrees. By using `(K, V)` as the separator, the
routing is always unambiguous regardless of key cardinality.

### Node recycling

Deleted nodes are not deallocated. Their indices are pushed onto a free list
and reused by subsequent allocations. This avoids Vec fragmentation and keeps
arena indices stable.

## License

Licensed under either of

- Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or
  http://www.apache.org/licenses/LICENSE-2.0)
- MIT License ([LICENSE-MIT](LICENSE-MIT) or
  http://opensource.org/licenses/MIT)

at your option.