# Benchmark Report: Sorted Maps and Sets

This report provides structured comparison tables and visual charts generated from benchmark results.

## System Environment and Metadata

| Attribute | Value |
|---|---|
| CPU | `AMD EPYC 9V45 96-Core Processor` |
| Operating System | `Linux-7.0.0-1019-azure-x86_64-with-glibc2.44` |
| CPU Frequency Governor | `None` |
| Native Allocator | `system malloc; Zig libc_allocator` |
| Compiler Optimization Flags | `ReleaseFast / Cargo release / -O3 / CMake Release` |
| Java Heap Settings | `-Xms1g -Xmx1g` |
| Git Revision | `780fc7da4e76f7a90e356507458deb44365ac4c8` |
| Timestamp (UTC) | `2026-11-05T18:27:16Z` |
| Toolchain Versions | Zig: 0.17.0, Rust: rustc 1.99.1 (58cf8f9c3 2026-10-13), C: gcc (GCC) 16.2.0, C++: g++ (GCC) 16.2.0, Java: openjdk version "25.0.4.1" 2026-08-18 |
| Runner environment | `GitHub-hosted CI` |
| Dirty working tree | `False` |
| Ordered source | `/nix/store/hfpp5dkf693h4dn27nznz230l3s4lbax-source` |
| Ordered local revision and changes | `None` |
| CPU affinity | `[0, 1, 2, 3]` |
| Warmups by language | `{'zig': 3, 'rust': 3, 'c': 3, 'cpp': 3, 'java': 20}` |
| Samples per fork | `5` |
| Forks | `3` |
| Fixture seeds | `[42, 123, 2026]` |
| Schedule seed | `1729` |

## Performance Interpretation Guide

Ascending and shuffled describe insertion order only. Lookup and removal use independent shuffled permutations. Containers are populated and validated before read and removal phases, so these measure recently accessed data. CI timings are exploratory; publish comparisons from a dedicated idle machine with recorded CPU affinity. This benchmark isolates five phases of sorted container operations:
- **Insert**: Time to insert $N$ keys into an initially empty container. Container construction and node allocation are included in new runs. Legacy Java runs excluded empty container construction. For ascending input, sequential B-tree optimizations are highlighted; for shuffled input, balancing overhead is tested.
- **Lookup hit**: Time to query $N$ keys that exist in the container. Measures pointer indirection, cache locality, and branching.
- **Lookup miss**: Time to query $N$ absent keys interleaved between existing keys. Tests traversal depth and early exit efficiency.
- **Iterate**: Time to perform an in-order scan across all elements. Highlights cache line density and memory locality (for example, flat arrays and B-tree leaf nodes versus pointer-chasing binary trees).
- **Remove**: Time to remove all $N$ keys until the container is empty. Native runners include node deallocation time. Java removal unlinks entries and does not force garbage collection.

Bold values mark the lowest measured median, not a proven winner.

### Architectural Comparisons

1. **B-trees versus binary trees**: B-trees (Ordered `BTreeMap`, Rust `BTreeMap`, Abseil `btree_map`, and Klib `kbtree`) pack multiple keys per node. This can reduce pointer chasing compared to node-allocated trees (`std::map`, Java `TreeMap`, and Zig `RedBlackTreeSet`).
2. **Intrusive and dedicated AVL trees**: Klib `kavl` and fastutil `AVLTreeMap` use strict AVL height balancing. Their balance rules differ from red-black trees. Measured latency also depends on node layout, allocation, and input.
3. **Flat arrays**: Boost `flat_map` and `flat_set` store elements in contiguous sorted memory. The layout can benefit reads, but random insertions and removals require shifting elements ($O(N)$ per operation), making large random mutation workloads expensive.
4. **Java boxed collections versus primitive specialization**: Java's standard `TreeMap<Long, Long>` stores boxed object pointers, incurring substantial GC and pointer overhead. The `fastutil` collections operate directly on primitive 64-bit integers (`long`), avoiding boxed key and value storage. Boxed inputs are prepared outside timers, so boxing allocation cost is excluded.

## Benchmark Results by Workload

### Workload: Size = 100,000 Elements (Ascending Keys, Seed 42)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 43.81 | 102.93 | 109.51 | 1.61 | 132.10 |
| C | Klib kavl | AVL Tree | 83.38 | 115.72 | 128.88 | 2.45 | 160.74 |
| C | Klib kbtree | B-tree | 44.92 | 113.06 | 114.72 | 1.56 | 208.90 |
| C++ | Abseil btree_map | B-tree | 25.85 | 54.52 | 56.18 | 0.42 | **69.74** |
| C++ | Boost flat_map | Flat Sorted Vector | 18.28 | 88.48 | 82.37 | **0.23** | 2617.65 |
| C++ | std::map | Red-Black Tree | 47.43 | 156.39 | 153.45 | 2.60 | 161.22 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 62.24 | 110.94 | 139.88 | 1.67 | 134.90 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 70.06 | 110.68 | 139.59 | 1.63 | 147.90 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 44.20 | 159.96 | 170.85 | 2.51 | 172.33 |
| Rust | std::collections::BTreeMap | B-tree | 39.95 | 71.35 | 72.30 | 0.91 | 91.16 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 34.00 | **47.53** | **46.41** | 0.29 | 101.26 |
| Zig | Ordered BTreeMap | B-tree (16-way) | **16.42** | 54.37 | 57.39 | 0.99 | 105.10 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 32.63 | 140.45 | 145.41 | 8.95 | 190.21 |
| Zig | Ordered SkipListMap | Skip List | 60.32 | 164.22 | 163.99 | 1.86 | 186.63 |
| Zig | std.Treap (Map) | Treap | 37.31 | 123.61 | 134.59 | 7.39 | 175.87 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 96
    bar [43.81, 83.38, 44.92, 25.85, 18.28, 47.43, 62.24, 70.06, 44.20, 39.95, 34.00, 16.42, 32.63, 60.32, 37.31]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 189
    bar [102.93, 115.72, 113.06, 54.52, 88.48, 156.39, 110.94, 110.68, 159.96, 71.35, 47.53, 54.37, 140.45, 164.22, 123.61]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 197
    bar [109.51, 128.88, 114.72, 56.18, 82.37, 153.45, 139.88, 139.59, 170.85, 72.30, 46.41, 57.39, 145.41, 163.99, 134.59]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 11
    bar [1.61, 2.45, 1.56, 0.42, 0.23, 2.60, 1.67, 1.63, 2.51, 0.91, 0.29, 0.99, 8.95, 1.86, 7.39]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 3011
    bar [132.10, 160.74, 208.90, 69.74, 2617.65, 161.22, 134.90, 147.90, 172.33, 91.16, 101.26, 105.10, 190.21, 186.63, 175.87]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 39.62 | 99.11 | 107.09 | 1.61 | 119.69 |
| C | Klib kavl | AVL Tree | 81.51 | 110.38 | 124.05 | 2.21 | 159.92 |
| C | Klib kbtree | B-tree | 37.38 | 106.06 | 106.42 | 1.46 | 196.89 |
| C++ | Abseil btree_set | B-tree | 26.56 | 45.96 | **45.07** | 0.32 | **66.33** |
| C++ | Boost flat_set | Flat Sorted Vector | **12.22** | 77.94 | 77.27 | **0.22** | 1233.60 |
| C++ | std::set | Red-Black Tree | 53.72 | 130.49 | 129.91 | 2.51 | 146.97 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 46.06 | 112.96 | 136.67 | 1.56 | 131.60 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 82.10 | 111.70 | 135.97 | 1.55 | 141.95 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 46.15 | 155.50 | 165.23 | 2.60 | 168.50 |
| Rust | std::collections::BTreeSet | B-tree | 38.38 | 71.21 | 71.44 | 0.79 | 83.10 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 16.53 | **45.76** | 45.66 | 0.28 | 88.50 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 37.44 | 120.87 | 133.42 | 3.25 | 149.79 |
| Zig | Ordered SortedSet | Sorted Vector | 16.65 | 80.29 | 85.48 | 0.22 | 1056.99 |
| Zig | std.Treap (Set) | Treap | 40.51 | 113.50 | 118.27 | 7.55 | 161.23 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 95
    bar [39.62, 81.51, 37.38, 26.56, 12.22, 53.72, 46.06, 82.10, 46.15, 38.38, 16.53, 37.44, 16.65, 40.51]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 179
    bar [99.11, 110.38, 106.06, 45.96, 77.94, 130.49, 112.96, 111.70, 155.50, 71.21, 45.76, 120.87, 80.29, 113.50]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 191
    bar [107.09, 124.05, 106.42, 45.07, 77.27, 129.91, 136.67, 135.97, 165.23, 71.44, 45.66, 133.42, 85.48, 118.27]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 9
    bar [1.61, 2.21, 1.46, 0.32, 0.22, 2.51, 1.56, 1.55, 2.60, 0.79, 0.28, 3.25, 0.22, 7.55]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 100,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1419
    bar [119.69, 159.92, 196.89, 66.33, 1233.60, 146.97, 131.60, 141.95, 168.50, 83.10, 88.50, 149.79, 1056.99, 161.23]
```

### Workload: Size = 100,000 Elements (Ascending Keys, Seed 123)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 44.88 | 103.10 | 109.13 | 1.61 | 132.34 |
| C | Klib kavl | AVL Tree | 83.55 | 118.45 | 131.15 | 2.40 | 161.53 |
| C | Klib kbtree | B-tree | 44.99 | 112.83 | 114.00 | 1.56 | 208.50 |
| C++ | Abseil btree_map | B-tree | 25.17 | 53.72 | 56.36 | 0.42 | **68.28** |
| C++ | Boost flat_map | Flat Sorted Vector | 18.16 | 87.53 | 82.77 | **0.23** | 2618.08 |
| C++ | std::map | Red-Black Tree | 46.94 | 156.59 | 147.27 | 2.56 | 155.73 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 61.84 | 111.05 | 140.48 | 1.66 | 134.50 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 70.16 | 110.54 | 139.75 | 1.63 | 149.11 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 44.51 | 158.99 | 170.69 | 2.55 | 173.67 |
| Rust | std::collections::BTreeMap | B-tree | 39.09 | 71.06 | 72.05 | 0.92 | 90.87 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 33.88 | **46.60** | **45.38** | 0.28 | 101.54 |
| Zig | Ordered BTreeMap | B-tree (16-way) | **16.53** | 53.94 | 57.19 | 0.99 | 104.63 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 32.56 | 141.10 | 144.95 | 8.89 | 188.33 |
| Zig | Ordered SkipListMap | Skip List | 60.14 | 163.87 | 162.64 | 1.86 | 184.56 |
| Zig | std.Treap (Map) | Treap | 36.66 | 125.91 | 128.16 | 7.36 | 169.82 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 97
    bar [44.88, 83.55, 44.99, 25.17, 18.16, 46.94, 61.84, 70.16, 44.51, 39.09, 33.88, 16.53, 32.56, 60.14, 36.66]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 189
    bar [103.10, 118.45, 112.83, 53.72, 87.53, 156.59, 111.05, 110.54, 158.99, 71.06, 46.60, 53.94, 141.10, 163.87, 125.91]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 197
    bar [109.13, 131.15, 114.00, 56.36, 82.77, 147.27, 140.48, 139.75, 170.69, 72.05, 45.38, 57.19, 144.95, 162.64, 128.16]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 11
    bar [1.61, 2.40, 1.56, 0.42, 0.23, 2.56, 1.66, 1.63, 2.55, 0.92, 0.28, 0.99, 8.89, 1.86, 7.36]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 3011
    bar [132.34, 161.53, 208.50, 68.28, 2618.08, 155.73, 134.50, 149.11, 173.67, 90.87, 101.54, 104.63, 188.33, 184.56, 169.82]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 39.35 | 99.91 | 107.27 | 1.61 | 120.23 |
| C | Klib kavl | AVL Tree | 81.31 | 113.03 | 126.37 | 2.23 | 160.25 |
| C | Klib kbtree | B-tree | 37.36 | 104.87 | 105.46 | 1.44 | 194.24 |
| C++ | Abseil btree_set | B-tree | 26.91 | 46.83 | **44.88** | 0.31 | **66.37** |
| C++ | Boost flat_set | Flat Sorted Vector | **12.25** | 78.18 | 77.58 | **0.22** | 1238.06 |
| C++ | std::set | Red-Black Tree | 54.57 | 131.99 | 132.90 | 2.50 | 151.10 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 46.16 | 114.31 | 136.14 | 1.56 | 131.21 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 82.06 | 112.02 | 135.02 | 1.56 | 142.23 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 45.59 | 155.12 | 167.18 | 2.65 | 171.20 |
| Rust | std::collections::BTreeSet | B-tree | 38.66 | 71.21 | 71.80 | 0.79 | 82.88 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 16.41 | **45.83** | 45.99 | 0.28 | 88.59 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 38.41 | 118.50 | 133.50 | 3.19 | 146.81 |
| Zig | Ordered SortedSet | Sorted Vector | 16.67 | 80.31 | 85.03 | 0.22 | 1054.69 |
| Zig | std.Treap (Set) | Treap | 37.58 | 119.56 | 118.68 | 7.41 | 160.83 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 95
    bar [39.35, 81.31, 37.36, 26.91, 12.25, 54.57, 46.16, 82.06, 45.59, 38.66, 16.41, 38.41, 16.67, 37.58]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 179
    bar [99.91, 113.03, 104.87, 46.83, 78.18, 131.99, 114.31, 112.02, 155.12, 71.21, 45.83, 118.50, 80.31, 119.56]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 193
    bar [107.27, 126.37, 105.46, 44.88, 77.58, 132.90, 136.14, 135.02, 167.18, 71.80, 45.99, 133.50, 85.03, 118.68]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 9
    bar [1.61, 2.23, 1.44, 0.31, 0.22, 2.50, 1.56, 1.56, 2.65, 0.79, 0.28, 3.19, 0.22, 7.41]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 100,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1424
    bar [120.23, 160.25, 194.24, 66.37, 1238.06, 151.10, 131.21, 142.23, 171.20, 82.88, 88.59, 146.81, 1054.69, 160.83]
```

### Workload: Size = 100,000 Elements (Ascending Keys, Seed 2026)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 44.55 | 107.08 | 114.13 | 1.61 | 132.63 |
| C | Klib kavl | AVL Tree | 83.11 | 116.43 | 129.11 | 2.42 | 160.04 |
| C | Klib kbtree | B-tree | 45.00 | 113.74 | 115.11 | 1.58 | 213.41 |
| C++ | Abseil btree_map | B-tree | 26.06 | 55.23 | 56.12 | 0.42 | **70.52** |
| C++ | Boost flat_map | Flat Sorted Vector | 18.30 | 88.40 | 83.19 | **0.23** | 2586.39 |
| C++ | std::map | Red-Black Tree | 46.21 | 149.41 | 150.06 | 2.58 | 160.04 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 61.72 | 110.68 | 140.13 | 1.65 | 135.62 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 70.02 | 110.67 | 139.85 | 1.64 | 148.42 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 44.24 | 160.33 | 169.73 | 2.55 | 173.08 |
| Rust | std::collections::BTreeMap | B-tree | 38.93 | 71.15 | 72.29 | 0.90 | 91.05 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 34.01 | **46.91** | **45.63** | 0.28 | 101.23 |
| Zig | Ordered BTreeMap | B-tree (16-way) | **17.03** | 54.16 | 57.18 | 0.99 | 105.01 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 32.57 | 140.57 | 143.82 | 8.89 | 186.81 |
| Zig | Ordered SkipListMap | Skip List | 60.20 | 160.93 | 161.17 | 1.88 | 184.85 |
| Zig | std.Treap (Map) | Treap | 36.62 | 125.28 | 136.26 | 7.35 | 174.29 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 96
    bar [44.55, 83.11, 45.00, 26.06, 18.30, 46.21, 61.72, 70.02, 44.24, 38.93, 34.01, 17.03, 32.57, 60.20, 36.62]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 186
    bar [107.08, 116.43, 113.74, 55.23, 88.40, 149.41, 110.68, 110.67, 160.33, 71.15, 46.91, 54.16, 140.57, 160.93, 125.28]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 196
    bar [114.13, 129.11, 115.11, 56.12, 83.19, 150.06, 140.13, 139.85, 169.73, 72.29, 45.63, 57.18, 143.82, 161.17, 136.26]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 11
    bar [1.61, 2.42, 1.58, 0.42, 0.23, 2.58, 1.65, 1.64, 2.55, 0.90, 0.28, 0.99, 8.89, 1.88, 7.35]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 2975
    bar [132.63, 160.04, 213.41, 70.52, 2586.39, 160.04, 135.62, 148.42, 173.08, 91.05, 101.23, 105.01, 186.81, 184.85, 174.29]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 39.29 | 94.08 | 102.02 | 1.61 | 119.27 |
| C | Klib kavl | AVL Tree | 80.85 | 108.17 | 122.15 | 2.21 | 158.52 |
| C | Klib kbtree | B-tree | 37.40 | 104.42 | 105.14 | 1.46 | 195.94 |
| C++ | Abseil btree_set | B-tree | 26.56 | **45.27** | **44.37** | 0.31 | **66.34** |
| C++ | Boost flat_set | Flat Sorted Vector | **12.44** | 78.29 | 77.82 | **0.22** | 1234.85 |
| C++ | std::set | Red-Black Tree | 49.71 | 130.56 | 134.14 | 2.54 | 145.32 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 45.97 | 114.34 | 135.56 | 1.56 | 131.75 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 81.53 | 113.16 | 135.75 | 1.55 | 141.14 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 44.88 | 154.04 | 166.10 | 2.57 | 171.66 |
| Rust | std::collections::BTreeSet | B-tree | 38.44 | 71.14 | 71.66 | 0.79 | 82.81 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 16.66 | 45.76 | 45.81 | 0.28 | 88.48 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 37.53 | 119.11 | 131.85 | 3.17 | 149.82 |
| Zig | Ordered SortedSet | Sorted Vector | 16.63 | 80.30 | 85.31 | 0.22 | 1052.70 |
| Zig | std.Treap (Set) | Treap | 37.61 | 114.78 | 120.92 | 7.54 | 162.48 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 94
    bar [39.29, 80.85, 37.40, 26.56, 12.44, 49.71, 45.97, 81.53, 44.88, 38.44, 16.66, 37.53, 16.63, 37.61]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 178
    bar [94.08, 108.17, 104.42, 45.27, 78.29, 130.56, 114.34, 113.16, 154.04, 71.14, 45.76, 119.11, 80.30, 114.78]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 192
    bar [102.02, 122.15, 105.14, 44.37, 77.82, 134.14, 135.56, 135.75, 166.10, 71.66, 45.81, 131.85, 85.31, 120.92]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 9
    bar [1.61, 2.21, 1.46, 0.31, 0.22, 2.54, 1.56, 1.55, 2.57, 0.79, 0.28, 3.17, 0.22, 7.54]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 100,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1421
    bar [119.27, 158.52, 195.94, 66.34, 1234.85, 145.32, 131.75, 141.14, 171.66, 82.81, 88.48, 149.82, 1052.70, 162.48]
```

### Workload: Size = 100,000 Elements (Shuffled Keys, Seed 42)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 136.25 | 107.61 | 117.06 | 1.65 | 130.55 |
| C | Klib kavl | AVL Tree | 173.30 | 115.97 | 134.69 | 9.27 | 170.46 |
| C | Klib kbtree | B-tree | 199.54 | 119.20 | 120.74 | 2.64 | 211.53 |
| C++ | Abseil btree_map | B-tree | **70.49** | 57.34 | 60.41 | 1.44 | **72.35** |
| C++ | Boost flat_map | Flat Sorted Vector | 2594.62 | 88.38 | 81.14 | **0.23** | 2604.39 |
| C++ | std::map | Red-Black Tree | 133.26 | 122.24 | 122.94 | 15.60 | 155.87 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 159.94 | 113.04 | 143.69 | 12.73 | 162.74 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 171.35 | 113.72 | 146.25 | 12.88 | 167.29 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 185.01 | 168.72 | 181.91 | 15.07 | 170.37 |
| Rust | std::collections::BTreeMap | B-tree | 76.96 | 71.16 | 71.93 | 2.49 | 88.65 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 159.27 | **45.05** | **44.12** | 0.27 | 106.80 |
| Zig | Ordered BTreeMap | B-tree (16-way) | 80.19 | 56.50 | 58.79 | 2.37 | 101.44 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 198.57 | 159.50 | 169.51 | 14.62 | 210.03 |
| Zig | Ordered SkipListMap | Skip List | 184.48 | 188.81 | 188.47 | 12.78 | 206.32 |
| Zig | std.Treap (Map) | Treap | 177.33 | 130.59 | 145.86 | 17.35 | 190.88 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 2984
    bar [136.25, 173.30, 199.54, 70.49, 2594.62, 133.26, 159.94, 171.35, 185.01, 76.96, 159.27, 80.19, 198.57, 184.48, 177.33]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 218
    bar [107.61, 115.97, 119.20, 57.34, 88.38, 122.24, 113.04, 113.72, 168.72, 71.16, 45.05, 56.50, 159.50, 188.81, 130.59]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 217
    bar [117.06, 134.69, 120.74, 60.41, 81.14, 122.94, 143.69, 146.25, 181.91, 71.93, 44.12, 58.79, 169.51, 188.47, 145.86]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 20
    bar [1.65, 9.27, 2.64, 1.44, 0.23, 15.60, 12.73, 12.88, 15.07, 2.49, 0.27, 2.37, 14.62, 12.78, 17.35]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 2996
    bar [130.55, 170.46, 211.53, 72.35, 2604.39, 155.87, 162.74, 167.29, 170.37, 88.65, 106.80, 101.44, 210.03, 206.32, 190.88]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 124.63 | 99.73 | 109.71 | 1.59 | 120.37 |
| C | Klib kavl | AVL Tree | 170.27 | 109.59 | 128.30 | 8.67 | 171.20 |
| C | Klib kbtree | B-tree | 180.50 | 105.27 | 105.14 | 2.41 | 192.45 |
| C++ | Abseil btree_set | B-tree | **65.58** | 47.49 | 47.34 | 0.70 | **67.43** |
| C++ | Boost flat_set | Flat Sorted Vector | 1244.45 | 78.17 | 77.49 | **0.22** | 1234.77 |
| C++ | std::set | Red-Black Tree | 91.78 | 123.05 | 123.27 | 15.51 | 153.29 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 142.03 | 108.13 | 139.62 | 12.39 | 155.16 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 143.73 | 109.27 | 142.74 | 12.47 | 167.43 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 187.29 | 166.25 | 179.36 | 15.96 | 174.72 |
| Rust | std::collections::BTreeSet | B-tree | 73.10 | 68.26 | 72.27 | 2.13 | 81.72 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 105.61 | **43.61** | **43.95** | 0.26 | 90.22 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 140.26 | 119.26 | 139.54 | 10.65 | 150.75 |
| Zig | Ordered SortedSet | Sorted Vector | 1217.03 | 80.32 | 85.16 | 0.22 | 1058.00 |
| Zig | std.Treap (Set) | Treap | 161.51 | 119.34 | 123.09 | 17.05 | 174.38 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1432
    bar [124.63, 170.27, 180.50, 65.58, 1244.45, 91.78, 142.03, 143.73, 187.29, 73.10, 105.61, 140.26, 1217.03, 161.51]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 192
    bar [99.73, 109.59, 105.27, 47.49, 78.17, 123.05, 108.13, 109.27, 166.25, 68.26, 43.61, 119.26, 80.32, 119.34]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 207
    bar [109.71, 128.30, 105.14, 47.34, 77.49, 123.27, 139.62, 142.74, 179.36, 72.27, 43.95, 139.54, 85.16, 123.09]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 20
    bar [1.59, 8.67, 2.41, 0.70, 0.22, 15.51, 12.39, 12.47, 15.96, 2.13, 0.26, 10.65, 0.22, 17.05]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 100,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1420
    bar [120.37, 171.20, 192.45, 67.43, 1234.77, 153.29, 155.16, 167.43, 174.72, 81.72, 90.22, 150.75, 1058.00, 174.38]
```

### Workload: Size = 100,000 Elements (Shuffled Keys, Seed 123)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 135.38 | 103.17 | 111.92 | 1.59 | 129.96 |
| C | Klib kavl | AVL Tree | 173.90 | 116.35 | 135.06 | 9.32 | 169.76 |
| C | Klib kbtree | B-tree | 194.17 | 115.33 | 116.80 | 2.64 | 207.49 |
| C++ | Abseil btree_map | B-tree | **72.72** | 60.72 | 60.94 | 1.46 | **74.71** |
| C++ | Boost flat_map | Flat Sorted Vector | 2629.73 | 88.50 | 83.02 | **0.23** | 2631.53 |
| C++ | std::map | Red-Black Tree | 126.89 | 122.10 | 121.58 | 15.45 | 151.84 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 162.20 | 110.57 | 142.61 | 12.85 | 162.51 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 170.64 | 112.54 | 144.04 | 12.89 | 167.71 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 183.59 | 168.81 | 183.04 | 14.99 | 174.54 |
| Rust | std::collections::BTreeMap | B-tree | 77.39 | 71.27 | 73.24 | 2.47 | 89.81 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 159.44 | **45.66** | **44.52** | 0.28 | 107.50 |
| Zig | Ordered BTreeMap | B-tree (16-way) | 79.53 | 56.86 | 59.08 | 2.36 | 102.24 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 194.64 | 160.03 | 168.38 | 14.54 | 205.68 |
| Zig | Ordered SkipListMap | Skip List | 186.94 | 196.04 | 196.24 | 12.84 | 208.93 |
| Zig | std.Treap (Map) | Treap | 164.55 | 118.59 | 133.90 | 17.45 | 185.30 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 3025
    bar [135.38, 173.90, 194.17, 72.72, 2629.73, 126.89, 162.20, 170.64, 183.59, 77.39, 159.44, 79.53, 194.64, 186.94, 164.55]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 226
    bar [103.17, 116.35, 115.33, 60.72, 88.50, 122.10, 110.57, 112.54, 168.81, 71.27, 45.66, 56.86, 160.03, 196.04, 118.59]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 226
    bar [111.92, 135.06, 116.80, 60.94, 83.02, 121.58, 142.61, 144.04, 183.04, 73.24, 44.52, 59.08, 168.38, 196.24, 133.90]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 21
    bar [1.59, 9.32, 2.64, 1.46, 0.23, 15.45, 12.85, 12.89, 14.99, 2.47, 0.28, 2.36, 14.54, 12.84, 17.45]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 3027
    bar [129.96, 169.76, 207.49, 74.71, 2631.53, 151.84, 162.51, 167.71, 174.54, 89.81, 107.50, 102.24, 205.68, 208.93, 185.30]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 123.83 | 99.70 | 109.51 | 1.59 | 122.41 |
| C | Klib kavl | AVL Tree | 170.21 | 110.03 | 128.88 | 8.87 | 171.26 |
| C | Klib kbtree | B-tree | 179.47 | 105.24 | 105.88 | 2.41 | 193.53 |
| C++ | Abseil btree_set | B-tree | **65.66** | 48.29 | 47.90 | 0.72 | **67.77** |
| C++ | Boost flat_set | Flat Sorted Vector | 1247.61 | 77.69 | 76.83 | **0.22** | 1236.86 |
| C++ | std::set | Red-Black Tree | 89.98 | 122.74 | 122.07 | 15.51 | 151.70 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 140.87 | 108.04 | 139.72 | 12.33 | 157.24 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 146.07 | 106.74 | 140.99 | 12.46 | 167.58 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 185.86 | 167.41 | 181.69 | 15.45 | 174.50 |
| Rust | std::collections::BTreeSet | B-tree | 72.06 | 68.03 | 70.10 | 2.14 | 80.59 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 105.25 | **43.34** | **43.13** | 0.26 | 89.93 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 141.08 | 119.64 | 139.55 | 10.74 | 155.36 |
| Zig | Ordered SortedSet | Sorted Vector | 1219.56 | 80.57 | 85.63 | **0.22** | 1055.44 |
| Zig | std.Treap (Set) | Treap | 152.97 | 110.36 | 118.43 | 17.30 | 171.48 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1435
    bar [123.83, 170.21, 179.47, 65.66, 1247.61, 89.98, 140.87, 146.07, 185.86, 72.06, 105.25, 141.08, 1219.56, 152.97]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 193
    bar [99.70, 110.03, 105.24, 48.29, 77.69, 122.74, 108.04, 106.74, 167.41, 68.03, 43.34, 119.64, 80.57, 110.36]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 209
    bar [109.51, 128.88, 105.88, 47.90, 76.83, 122.07, 139.72, 140.99, 181.69, 70.10, 43.13, 139.55, 85.63, 118.43]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 20
    bar [1.59, 8.87, 2.41, 0.72, 0.22, 15.51, 12.33, 12.46, 15.45, 2.14, 0.26, 10.74, 0.22, 17.30]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 100,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1423
    bar [122.41, 171.26, 193.53, 67.77, 1236.86, 151.70, 157.24, 167.58, 174.50, 80.59, 89.93, 155.36, 1055.44, 171.48]
```

### Workload: Size = 100,000 Elements (Shuffled Keys, Seed 2026)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 137.25 | 107.84 | 117.14 | 1.59 | 131.57 |
| C | Klib kavl | AVL Tree | 175.64 | 116.19 | 134.88 | 9.62 | 180.74 |
| C | Klib kbtree | B-tree | 199.39 | 118.98 | 122.86 | 2.72 | 216.95 |
| C++ | Abseil btree_map | B-tree | **71.84** | 60.54 | 61.54 | 1.49 | **74.58** |
| C++ | Boost flat_map | Flat Sorted Vector | 2615.86 | 88.53 | 84.27 | **0.23** | 2619.38 |
| C++ | std::map | Red-Black Tree | 131.19 | 124.30 | 122.23 | 15.78 | 154.36 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 165.66 | 113.30 | 145.56 | 12.83 | 170.02 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 186.96 | 125.17 | 155.43 | 13.90 | 167.68 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 207.96 | 181.02 | 187.18 | 16.20 | 174.14 |
| Rust | std::collections::BTreeMap | B-tree | 78.75 | 71.83 | 71.41 | 2.48 | 88.92 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 160.72 | **46.04** | **44.75** | 0.28 | 107.05 |
| Zig | Ordered BTreeMap | B-tree (16-way) | 81.15 | 55.20 | 57.48 | 2.35 | 102.52 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 197.98 | 161.05 | 171.45 | 14.64 | 208.86 |
| Zig | Ordered SkipListMap | Skip List | 190.66 | 191.30 | 190.57 | 13.01 | 207.92 |
| Zig | std.Treap (Map) | Treap | 167.94 | 121.16 | 135.76 | 17.50 | 189.42 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 3009
    bar [137.25, 175.64, 199.39, 71.84, 2615.86, 131.19, 165.66, 186.96, 207.96, 78.75, 160.72, 81.15, 197.98, 190.66, 167.94]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 220
    bar [107.84, 116.19, 118.98, 60.54, 88.53, 124.30, 113.30, 125.17, 181.02, 71.83, 46.04, 55.20, 161.05, 191.30, 121.16]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 220
    bar [117.14, 134.88, 122.86, 61.54, 84.27, 122.23, 145.56, 155.43, 187.18, 71.41, 44.75, 57.48, 171.45, 190.57, 135.76]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 21
    bar [1.59, 9.62, 2.72, 1.49, 0.23, 15.78, 12.83, 13.90, 16.20, 2.48, 0.28, 2.35, 14.64, 13.01, 17.50]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 3013
    bar [131.57, 180.74, 216.95, 74.58, 2619.38, 154.36, 170.02, 167.68, 174.14, 88.92, 107.05, 102.52, 208.86, 207.92, 189.42]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 123.73 | 100.13 | 110.21 | 1.59 | 120.89 |
| C | Klib kavl | AVL Tree | 169.99 | 110.16 | 128.27 | 8.70 | 170.80 |
| C | Klib kbtree | B-tree | 180.30 | 105.81 | 105.32 | 2.42 | 193.93 |
| C++ | Abseil btree_set | B-tree | **66.05** | 48.84 | 48.60 | 0.74 | **68.66** |
| C++ | Boost flat_set | Flat Sorted Vector | 1248.57 | 77.91 | 77.13 | **0.22** | 1235.62 |
| C++ | std::set | Red-Black Tree | 91.55 | 123.92 | 122.31 | 15.21 | 149.33 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 143.90 | 107.31 | 142.13 | 12.28 | 157.16 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 147.59 | 109.48 | 142.38 | 12.55 | 169.38 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 190.09 | 169.08 | 185.94 | 16.19 | 179.64 |
| Rust | std::collections::BTreeSet | B-tree | 72.57 | 68.09 | 70.98 | 2.17 | 80.59 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 106.02 | **43.86** | **44.10** | 0.26 | 90.25 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 138.87 | 120.37 | 140.70 | 10.81 | 156.66 |
| Zig | Ordered SortedSet | Sorted Vector | 1224.84 | 81.00 | 85.72 | 0.22 | 1055.69 |
| Zig | std.Treap (Set) | Treap | 155.36 | 110.78 | 121.07 | 17.43 | 172.61 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1436
    bar [123.73, 169.99, 180.30, 66.05, 1248.57, 91.55, 143.90, 147.59, 190.09, 72.57, 106.02, 138.87, 1224.84, 155.36]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 195
    bar [100.13, 110.16, 105.81, 48.84, 77.91, 123.92, 107.31, 109.48, 169.08, 68.09, 43.86, 120.37, 81.00, 110.78]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 214
    bar [110.21, 128.27, 105.32, 48.60, 77.13, 122.31, 142.13, 142.38, 185.94, 70.98, 44.10, 140.70, 85.72, 121.07]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 21
    bar [1.59, 8.70, 2.42, 0.74, 0.22, 15.21, 12.28, 12.55, 16.19, 2.17, 0.26, 10.81, 0.22, 17.43]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 100,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1421
    bar [120.89, 170.80, 193.93, 68.66, 1235.62, 149.33, 157.16, 169.38, 179.64, 80.59, 90.25, 156.66, 1055.69, 172.61]
```

### Workload: Size = 1,000 Elements (Ascending Keys, Seed 42)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 22.04 | 44.54 | 50.29 | 1.63 | 60.22 |
| C | Klib kavl | AVL Tree | 59.85 | 43.27 | 49.66 | 2.55 | 72.11 |
| C | Klib kbtree | B-tree | 27.56 | 49.05 | 51.18 | 1.56 | 95.10 |
| C++ | Abseil btree_map | B-tree | 19.41 | 21.06 | 19.99 | 0.44 | 35.49 |
| C++ | Boost flat_map | Flat Sorted Vector | **5.27** | 34.32 | 32.83 | **0.26** | 45.99 |
| C++ | std::map | Red-Black Tree | 23.77 | 32.65 | 35.14 | 2.63 | 52.69 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 57.24 | 88.02 | 64.07 | 40.83 | 111.45 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 136.68 | 91.95 | 84.29 | 42.00 | 972.17 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 53.48 | 68.11 | 53.06 | 68.30 | 76.36 |
| Rust | std::collections::BTreeMap | B-tree | 30.20 | 27.06 | 27.17 | 0.64 | 49.63 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 21.86 | **11.29** | **10.68** | 0.29 | 38.40 |
| Zig | Ordered BTreeMap | B-tree (16-way) | 9.22 | 13.66 | 15.00 | 0.86 | **31.50** |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 25.32 | 37.57 | 35.61 | 7.64 | 67.79 |
| Zig | Ordered SkipListMap | Skip List | 60.38 | 47.76 | 47.80 | 2.24 | 66.10 |
| Zig | std.Treap (Map) | Treap | 34.69 | 42.00 | 48.14 | 7.54 | 67.75 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 158
    bar [22.04, 59.85, 27.56, 19.41, 5.27, 23.77, 57.24, 136.68, 53.48, 30.20, 21.86, 9.22, 25.32, 60.38, 34.69]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 106
    bar [44.54, 43.27, 49.05, 21.06, 34.32, 32.65, 88.02, 91.95, 68.11, 27.06, 11.29, 13.66, 37.57, 47.76, 42.00]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 97
    bar [50.29, 49.66, 51.18, 19.99, 32.83, 35.14, 64.07, 84.29, 53.06, 27.17, 10.68, 15.00, 35.61, 47.80, 48.14]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 79
    bar [1.63, 2.55, 1.56, 0.44, 0.26, 2.63, 40.83, 42.00, 68.30, 0.64, 0.29, 0.86, 7.64, 2.24, 7.54]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 1118
    bar [60.22, 72.11, 95.10, 35.49, 45.99, 52.69, 111.45, 972.17, 76.36, 49.63, 38.40, 31.50, 67.79, 66.10, 67.75]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 21.95 | 45.54 | 50.37 | 1.62 | 57.51 |
| C | Klib kavl | AVL Tree | 60.80 | 39.85 | 45.95 | 2.37 | 71.36 |
| C | Klib kbtree | B-tree | 22.20 | 48.73 | 51.53 | 1.56 | 91.70 |
| C++ | Abseil btree_set | B-tree | 19.64 | 19.49 | 19.71 | 0.37 | **34.87** |
| C++ | Boost flat_set | Flat Sorted Vector | **4.95** | 32.75 | 32.74 | **0.15** | 36.41 |
| C++ | std::set | Red-Black Tree | 32.68 | 29.80 | 30.39 | 2.44 | 50.37 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 52.83 | 70.89 | 74.16 | 41.89 | 109.19 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 1634.29 | 59.34 | 70.80 | 42.22 | 879.53 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 59.29 | 81.87 | 57.94 | 53.19 | 116.94 |
| Rust | std::collections::BTreeSet | B-tree | 29.68 | 29.00 | 26.82 | 0.85 | 42.53 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 8.85 | **11.24** | **11.25** | 0.28 | 36.54 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 25.60 | 31.67 | 39.00 | 2.90 | 57.53 |
| Zig | Ordered SortedSet | Sorted Vector | 8.75 | 32.93 | 38.13 | 0.23 | 43.16 |
| Zig | std.Treap (Set) | Treap | 35.97 | 40.78 | 44.47 | 7.34 | 65.61 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1880
    bar [21.95, 60.80, 22.20, 19.64, 4.95, 32.68, 52.83, 1634.29, 59.29, 29.68, 8.85, 25.60, 8.75, 35.97]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 95
    bar [45.54, 39.85, 48.73, 19.49, 32.75, 29.80, 70.89, 59.34, 81.87, 29.00, 11.24, 31.67, 32.93, 40.78]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 86
    bar [50.37, 45.95, 51.53, 19.71, 32.74, 30.39, 74.16, 70.80, 57.94, 26.82, 11.25, 39.00, 38.13, 44.47]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 62
    bar [1.62, 2.37, 1.56, 0.37, 0.15, 2.44, 41.89, 42.22, 53.19, 0.85, 0.28, 2.90, 0.23, 7.34]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 1,000, Ascending Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1012
    bar [57.51, 71.36, 91.70, 34.87, 36.41, 50.37, 109.19, 879.53, 116.94, 42.53, 36.54, 57.53, 43.16, 65.61]
```

### Workload: Size = 1,000 Elements (Ascending Keys, Seed 123)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 21.99 | 45.45 | 51.02 | 1.65 | 57.49 |
| C | Klib kavl | AVL Tree | 59.71 | 43.70 | 51.13 | 2.51 | 72.48 |
| C | Klib kbtree | B-tree | 27.62 | 49.72 | 51.02 | 1.54 | 97.04 |
| C++ | Abseil btree_map | B-tree | 19.66 | 19.71 | 20.40 | 0.46 | 35.18 |
| C++ | Boost flat_map | Flat Sorted Vector | **5.23** | 34.18 | 32.57 | **0.26** | 46.10 |
| C++ | std::map | Red-Black Tree | 23.32 | 33.86 | 34.24 | 2.62 | 53.88 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 65.72 | 88.01 | 70.54 | 42.07 | 115.64 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 132.52 | 90.43 | 73.98 | 41.71 | 928.38 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 72.94 | 67.76 | 51.28 | 69.78 | 76.58 |
| Rust | std::collections::BTreeMap | B-tree | 30.62 | 27.39 | 26.14 | 0.63 | 48.79 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 21.85 | **11.30** | **10.68** | 0.29 | 39.05 |
| Zig | Ordered BTreeMap | B-tree (16-way) | 9.27 | 13.61 | 14.76 | 0.86 | **31.05** |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 25.66 | 39.64 | 35.58 | 7.59 | 66.70 |
| Zig | Ordered SkipListMap | Skip List | 60.38 | 47.10 | 47.53 | 2.26 | 66.32 |
| Zig | std.Treap (Map) | Treap | 35.63 | 43.20 | 43.23 | 7.86 | 70.69 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 153
    bar [21.99, 59.71, 27.62, 19.66, 5.23, 23.32, 65.72, 132.52, 72.94, 30.62, 21.85, 9.27, 25.66, 60.38, 35.63]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 104
    bar [45.45, 43.70, 49.72, 19.71, 34.18, 33.86, 88.01, 90.43, 67.76, 27.39, 11.30, 13.61, 39.64, 47.10, 43.20]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 86
    bar [51.02, 51.13, 51.02, 20.40, 32.57, 34.24, 70.54, 73.98, 51.28, 26.14, 10.68, 14.76, 35.58, 47.53, 43.23]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 81
    bar [1.65, 2.51, 1.54, 0.46, 0.26, 2.62, 42.07, 41.71, 69.78, 0.63, 0.29, 0.86, 7.59, 2.26, 7.86]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 1068
    bar [57.49, 72.48, 97.04, 35.18, 46.10, 53.88, 115.64, 928.38, 76.58, 48.79, 39.05, 31.05, 66.70, 66.32, 70.69]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 21.88 | 41.89 | 47.40 | 1.62 | 51.96 |
| C | Klib kavl | AVL Tree | 61.85 | 40.58 | 47.36 | 2.33 | 72.41 |
| C | Klib kbtree | B-tree | 22.13 | 48.92 | 51.97 | 1.55 | 90.36 |
| C++ | Abseil btree_set | B-tree | 19.55 | 19.95 | 19.23 | 0.38 | **34.90** |
| C++ | Boost flat_set | Flat Sorted Vector | **4.88** | 32.44 | 33.57 | **0.15** | 36.55 |
| C++ | std::set | Red-Black Tree | 32.10 | 29.27 | 30.48 | 2.45 | 52.97 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 82.70 | 60.42 | 66.28 | 41.37 | 131.30 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 1189.49 | 97.35 | 75.72 | 41.58 | 185.16 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 57.70 | 72.06 | 67.61 | 53.22 | 136.85 |
| Rust | std::collections::BTreeSet | B-tree | 29.03 | 28.31 | 26.19 | 0.87 | 41.20 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 8.85 | **11.25** | **11.26** | 0.28 | 36.71 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 25.99 | 32.94 | 39.75 | 2.88 | 58.43 |
| Zig | Ordered SortedSet | Sorted Vector | 8.81 | 33.06 | 39.21 | 0.23 | 43.52 |
| Zig | std.Treap (Set) | Treap | 37.80 | 39.93 | 45.48 | 7.44 | 69.05 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1368
    bar [21.88, 61.85, 22.13, 19.55, 4.88, 32.10, 82.70, 1189.49, 57.70, 29.03, 8.85, 25.99, 8.81, 37.80]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 112
    bar [41.89, 40.58, 48.92, 19.95, 32.44, 29.27, 60.42, 97.35, 72.06, 28.31, 11.25, 32.94, 33.06, 39.93]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 88
    bar [47.40, 47.36, 51.97, 19.23, 33.57, 30.48, 66.28, 75.72, 67.61, 26.19, 11.26, 39.75, 39.21, 45.48]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 62
    bar [1.62, 2.33, 1.55, 0.38, 0.15, 2.45, 41.37, 41.58, 53.22, 0.87, 0.28, 2.88, 0.23, 7.44]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 1,000, Ascending Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 213
    bar [51.96, 72.41, 90.36, 34.90, 36.55, 52.97, 131.30, 185.16, 136.85, 41.20, 36.71, 58.43, 43.52, 69.05]
```

### Workload: Size = 1,000 Elements (Ascending Keys, Seed 2026)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 22.00 | 46.02 | 51.43 | 1.62 | 58.89 |
| C | Klib kavl | AVL Tree | 60.72 | 43.44 | 50.77 | 2.49 | 73.30 |
| C | Klib kbtree | B-tree | 27.71 | 48.22 | 51.00 | 1.55 | 96.59 |
| C++ | Abseil btree_map | B-tree | 19.49 | 20.15 | 20.59 | 0.48 | 35.53 |
| C++ | Boost flat_map | Flat Sorted Vector | **5.22** | 33.07 | 33.21 | **0.26** | 46.78 |
| C++ | std::map | Red-Black Tree | 23.42 | 32.80 | 34.41 | 2.61 | 53.28 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 57.90 | 83.31 | 65.12 | 39.92 | 111.38 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 723.00 | 123.22 | 77.48 | 41.94 | 915.44 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 53.58 | 70.79 | 51.98 | 69.39 | 70.90 |
| Rust | std::collections::BTreeMap | B-tree | 30.16 | 27.32 | 27.49 | 0.66 | 47.42 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 21.93 | **11.27** | **10.64** | 0.28 | 39.24 |
| Zig | Ordered BTreeMap | B-tree (16-way) | 9.18 | 13.79 | 14.92 | 0.87 | **31.22** |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 25.53 | 37.97 | 36.56 | 7.70 | 69.00 |
| Zig | Ordered SkipListMap | Skip List | 60.92 | 48.25 | 47.94 | 2.26 | 70.03 |
| Zig | std.Treap (Map) | Treap | 34.93 | 42.79 | 45.36 | 7.59 | 71.76 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 832
    bar [22.00, 60.72, 27.71, 19.49, 5.22, 23.42, 57.90, 723.00, 53.58, 30.16, 21.93, 9.18, 25.53, 60.92, 34.93]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 142
    bar [46.02, 43.44, 48.22, 20.15, 33.07, 32.80, 83.31, 123.22, 70.79, 27.32, 11.27, 13.79, 37.97, 48.25, 42.79]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 90
    bar [51.43, 50.77, 51.00, 20.59, 33.21, 34.41, 65.12, 77.48, 51.98, 27.49, 10.64, 14.92, 36.56, 47.94, 45.36]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 80
    bar [1.62, 2.49, 1.55, 0.48, 0.26, 2.61, 39.92, 41.94, 69.39, 0.66, 0.28, 0.87, 7.70, 2.26, 7.59]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 1053
    bar [58.89, 73.30, 96.59, 35.53, 46.78, 53.28, 111.38, 915.44, 70.90, 47.42, 39.24, 31.22, 69.00, 70.03, 71.76]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 21.92 | 47.38 | 52.42 | 1.62 | 54.99 |
| C | Klib kavl | AVL Tree | 61.58 | 40.71 | 46.96 | 2.34 | 73.84 |
| C | Klib kbtree | B-tree | 22.09 | 48.35 | 51.21 | 1.52 | 89.28 |
| C++ | Abseil btree_set | B-tree | 24.01 | 20.37 | 19.56 | 0.37 | **34.80** |
| C++ | Boost flat_set | Flat Sorted Vector | **4.96** | 33.89 | 33.93 | **0.15** | 38.19 |
| C++ | std::set | Red-Black Tree | 32.53 | 30.27 | 29.70 | 2.51 | 51.34 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 52.39 | 59.86 | 74.67 | 42.51 | 122.58 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 1250.53 | 66.87 | 75.59 | 42.52 | 279.75 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 76.57 | 76.27 | 82.34 | 55.22 | 132.96 |
| Rust | std::collections::BTreeSet | B-tree | 29.41 | 28.69 | 27.32 | 0.84 | 40.78 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 8.94 | **11.26** | **11.28** | 0.28 | 36.67 |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 25.99 | 34.89 | 39.70 | 2.88 | 57.17 |
| Zig | Ordered SortedSet | Sorted Vector | 8.78 | 34.51 | 38.48 | 0.23 | 43.53 |
| Zig | std.Treap (Set) | Treap | 35.48 | 40.09 | 44.95 | 7.61 | 69.58 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 1439
    bar [21.92, 61.58, 22.09, 24.01, 4.96, 32.53, 52.39, 1250.53, 76.57, 29.41, 8.94, 25.99, 8.78, 35.48]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 88
    bar [47.38, 40.71, 48.35, 20.37, 33.89, 30.27, 59.86, 66.87, 76.27, 28.69, 11.26, 34.89, 34.51, 40.09]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 95
    bar [52.42, 46.96, 51.21, 19.56, 33.93, 29.70, 74.67, 75.59, 82.34, 27.32, 11.28, 39.70, 38.48, 44.95]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 64
    bar [1.62, 2.34, 1.52, 0.37, 0.15, 2.51, 42.51, 42.52, 55.22, 0.84, 0.28, 2.88, 0.23, 7.61]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 1,000, Ascending Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 322
    bar [54.99, 73.84, 89.28, 34.80, 38.19, 51.34, 122.58, 279.75, 132.96, 40.78, 36.67, 57.17, 43.53, 69.58]
```

### Workload: Size = 1,000 Elements (Shuffled Keys, Seed 42)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 67.01 | 53.00 | 58.31 | 1.62 | 66.43 |
| C | Klib kavl | AVL Tree | 79.07 | 43.44 | 49.62 | 6.56 | 79.88 |
| C | Klib kbtree | B-tree | 97.16 | 56.20 | 55.60 | 2.64 | 110.35 |
| C++ | Abseil btree_map | B-tree | 42.21 | 23.77 | 23.35 | 0.72 | **39.98** |
| C++ | Boost flat_map | Flat Sorted Vector | 52.05 | 44.43 | 41.47 | **0.26** | 53.08 |
| C++ | std::map | Red-Black Tree | 62.77 | 37.18 | 37.49 | 6.27 | 60.44 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 97.65 | 82.78 | 78.61 | 40.89 | 119.10 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 185.63 | 83.12 | 68.97 | 41.63 | 349.02 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 86.72 | 79.21 | 63.15 | 72.27 | 96.57 |
| Rust | std::collections::BTreeMap | B-tree | 47.15 | 28.58 | 29.62 | 1.45 | 49.38 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 62.25 | **11.31** | **10.73** | 0.29 | 40.80 |
| Zig | Ordered BTreeMap | B-tree (16-way) | **33.07** | 18.92 | 20.15 | 2.08 | 46.93 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 73.98 | 40.50 | 40.17 | 8.40 | 73.59 |
| Zig | Ordered SkipListMap | Skip List | 78.11 | 51.59 | 50.94 | 2.98 | 70.24 |
| Zig | std.Treap (Map) | Treap | 57.91 | 32.24 | 35.75 | 9.22 | 64.59 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 214
    bar [67.01, 79.07, 97.16, 42.21, 52.05, 62.77, 97.65, 185.63, 86.72, 47.15, 62.25, 33.07, 73.98, 78.11, 57.91]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 96
    bar [53.00, 43.44, 56.20, 23.77, 44.43, 37.18, 82.78, 83.12, 79.21, 28.58, 11.31, 18.92, 40.50, 51.59, 32.24]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 91
    bar [58.31, 49.62, 55.60, 23.35, 41.47, 37.49, 78.61, 68.97, 63.15, 29.62, 10.73, 20.15, 40.17, 50.94, 35.75]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 84
    bar [1.62, 6.56, 2.64, 0.72, 0.26, 6.27, 40.89, 41.63, 72.27, 1.45, 0.29, 2.08, 8.40, 2.98, 9.22]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 402
    bar [66.43, 79.88, 110.35, 39.98, 53.08, 60.44, 119.10, 349.02, 96.57, 49.38, 40.80, 46.93, 73.59, 70.24, 64.59]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 64.56 | 53.05 | 58.97 | 1.62 | 64.24 |
| C | Klib kavl | AVL Tree | 82.30 | 41.60 | 47.21 | 5.91 | 79.15 |
| C | Klib kbtree | B-tree | 92.89 | 55.29 | 54.02 | 2.42 | 103.17 |
| C++ | Abseil btree_set | B-tree | 38.88 | 22.46 | 23.16 | 0.59 | 41.99 |
| C++ | Boost flat_set | Flat Sorted Vector | 44.44 | 42.55 | 41.30 | **0.15** | 44.13 |
| C++ | std::set | Red-Black Tree | 45.99 | 33.93 | 34.46 | 5.00 | 56.38 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 77.33 | 67.04 | 72.05 | 42.61 | 99.58 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 172.53 | 53.30 | 64.53 | 43.28 | 291.78 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 121.54 | 100.92 | 74.88 | 71.83 | 132.49 |
| Rust | std::collections::BTreeSet | B-tree | **37.07** | 29.00 | 29.03 | 1.43 | 42.03 |
| Rust | indexset::BTreeSet | Two-Level B-tree | 38.04 | **11.24** | **11.26** | 0.28 | **38.16** |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 62.81 | 40.62 | 47.26 | 6.36 | 61.40 |
| Zig | Ordered SortedSet | Sorted Vector | 37.51 | 38.32 | 44.23 | 0.23 | 45.43 |
| Zig | std.Treap (Set) | Treap | 58.44 | 31.54 | 34.35 | 7.53 | 62.12 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 199
    bar [64.56, 82.30, 92.89, 38.88, 44.44, 45.99, 77.33, 172.53, 121.54, 37.07, 38.04, 62.81, 37.51, 58.44]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 117
    bar [53.05, 41.60, 55.29, 22.46, 42.55, 33.93, 67.04, 53.30, 100.92, 29.00, 11.24, 40.62, 38.32, 31.54]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 87
    bar [58.97, 47.21, 54.02, 23.16, 41.30, 34.46, 72.05, 64.53, 74.88, 29.03, 11.26, 47.26, 44.23, 34.35]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 83
    bar [1.62, 5.91, 2.42, 0.59, 0.15, 5.00, 42.61, 43.28, 71.83, 1.43, 0.28, 6.36, 0.23, 7.53]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 1,000, Shuffled Keys, Seed 42)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 336
    bar [64.24, 79.15, 103.17, 41.99, 44.13, 56.38, 99.58, 291.78, 132.49, 42.03, 38.16, 61.40, 45.43, 62.12]
```

### Workload: Size = 1,000 Elements (Shuffled Keys, Seed 123)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 66.04 | 51.82 | 56.71 | 1.62 | 68.13 |
| C | Klib kavl | AVL Tree | 78.91 | 44.60 | 50.61 | 6.19 | 79.53 |
| C | Klib kbtree | B-tree | 97.50 | 56.92 | 56.23 | 2.58 | 107.48 |
| C++ | Abseil btree_map | B-tree | 40.57 | 22.44 | 22.65 | 0.78 | **40.42** |
| C++ | Boost flat_map | Flat Sorted Vector | 52.06 | 44.22 | 41.27 | **0.26** | 54.11 |
| C++ | std::map | Red-Black Tree | 60.24 | 36.52 | 38.44 | 6.22 | 59.17 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 104.74 | 85.00 | 72.10 | 41.73 | 116.90 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 167.45 | 88.24 | 51.90 | 41.60 | 318.86 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 90.23 | 76.67 | 68.97 | 71.34 | 104.47 |
| Rust | std::collections::BTreeMap | B-tree | 42.07 | 26.92 | 27.72 | 1.31 | 46.74 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 60.29 | **11.31** | **10.71** | 0.28 | 41.00 |
| Zig | Ordered BTreeMap | B-tree (16-way) | **35.77** | 19.30 | 20.82 | 2.12 | 46.91 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 76.36 | 42.41 | 41.12 | 8.37 | 72.38 |
| Zig | Ordered SkipListMap | Skip List | 75.72 | 47.76 | 48.08 | 3.00 | 68.86 |
| Zig | std.Treap (Map) | Treap | 58.33 | 32.06 | 36.10 | 9.00 | 65.13 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 193
    bar [66.04, 78.91, 97.50, 40.57, 52.06, 60.24, 104.74, 167.45, 90.23, 42.07, 60.29, 35.77, 76.36, 75.72, 58.33]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 102
    bar [51.82, 44.60, 56.92, 22.44, 44.22, 36.52, 85.00, 88.24, 76.67, 26.92, 11.31, 19.30, 42.41, 47.76, 32.06]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 83
    bar [56.71, 50.61, 56.23, 22.65, 41.27, 38.44, 72.10, 51.90, 68.97, 27.72, 10.71, 20.82, 41.12, 48.08, 36.10]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 83
    bar [1.62, 6.19, 2.58, 0.78, 0.26, 6.22, 41.73, 41.60, 71.34, 1.31, 0.28, 2.12, 8.37, 3.00, 9.00]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 367
    bar [68.13, 79.53, 107.48, 40.42, 54.11, 59.17, 116.90, 318.86, 104.47, 46.74, 41.00, 46.91, 72.38, 68.86, 65.13]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 64.43 | 51.73 | 57.18 | 1.63 | 64.63 |
| C | Klib kavl | AVL Tree | 82.88 | 41.34 | 47.16 | 5.72 | 78.76 |
| C | Klib kbtree | B-tree | 92.96 | 57.13 | 55.06 | 2.46 | 104.52 |
| C++ | Abseil btree_set | B-tree | 42.38 | 22.64 | 22.79 | 0.60 | 41.79 |
| C++ | Boost flat_set | Flat Sorted Vector | 43.87 | 42.48 | 41.18 | **0.15** | 44.86 |
| C++ | std::set | Red-Black Tree | 45.47 | 34.60 | 34.14 | 4.99 | 54.19 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 83.23 | 66.14 | 64.11 | 42.98 | 94.98 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 183.08 | 62.19 | 66.03 | 42.99 | 289.85 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 124.77 | 112.54 | 94.60 | 56.57 | 128.09 |
| Rust | std::collections::BTreeSet | B-tree | 38.41 | 29.10 | 29.05 | 1.42 | 40.45 |
| Rust | indexset::BTreeSet | Two-Level B-tree | **34.26** | **11.25** | **11.28** | 0.28 | **38.14** |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 62.78 | 39.97 | 46.34 | 6.20 | 59.92 |
| Zig | Ordered SortedSet | Sorted Vector | 37.88 | 37.21 | 44.84 | 0.23 | 47.39 |
| Zig | std.Treap (Set) | Treap | 57.31 | 30.44 | 34.75 | 7.42 | 62.70 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 211
    bar [64.43, 82.88, 92.96, 42.38, 43.87, 45.47, 83.23, 183.08, 124.77, 38.41, 34.26, 62.78, 37.88, 57.31]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 130
    bar [51.73, 41.34, 57.13, 22.64, 42.48, 34.60, 66.14, 62.19, 112.54, 29.10, 11.25, 39.97, 37.21, 30.44]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 109
    bar [57.18, 47.16, 55.06, 22.79, 41.18, 34.14, 64.11, 66.03, 94.60, 29.05, 11.28, 46.34, 44.84, 34.75]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 66
    bar [1.63, 5.72, 2.46, 0.60, 0.15, 4.99, 42.98, 42.99, 56.57, 1.42, 0.28, 6.20, 0.23, 7.42]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 1,000, Shuffled Keys, Seed 123)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 334
    bar [64.63, 78.76, 104.52, 41.79, 44.86, 54.19, 94.98, 289.85, 128.09, 40.45, 38.14, 59.92, 47.39, 62.70]
```

### Workload: Size = 1,000 Elements (Shuffled Keys, Seed 2026)

#### Sorted Maps

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 66.18 | 52.32 | 57.34 | 1.61 | 67.14 |
| C | Klib kavl | AVL Tree | 79.12 | 43.72 | 48.86 | 6.08 | 80.05 |
| C | Klib kbtree | B-tree | 97.43 | 57.21 | 57.31 | 2.53 | 107.50 |
| C++ | Abseil btree_map | B-tree | 41.78 | 22.05 | 23.25 | 0.71 | **39.92** |
| C++ | Boost flat_map | Flat Sorted Vector | 52.40 | 42.01 | 41.17 | **0.26** | 53.72 |
| C++ | std::map | Red-Black Tree | 60.19 | 37.60 | 38.15 | 6.14 | 58.93 |
| Java | fastutil AVLTreeMap | AVL Tree (primitive long) | 71.83 | 83.49 | 72.71 | 41.50 | 114.67 |
| Java | fastutil RBTreeMap | Red-Black Tree (primitive long) | 256.88 | 91.27 | 52.94 | 41.84 | 311.80 |
| Java | java.util.TreeMap | Red-Black Tree (boxed Long) | 84.04 | 82.83 | 78.44 | 71.63 | 106.68 |
| Rust | std::collections::BTreeMap | B-tree | 42.69 | 28.26 | 28.28 | 1.42 | 48.82 |
| Rust | indexset::BTreeMap | Two-Level B-tree | 58.12 | **11.30** | **10.60** | 0.29 | 41.33 |
| Zig | Ordered BTreeMap | B-tree (16-way) | **35.09** | 19.34 | 20.52 | 2.09 | 47.03 |
| Zig | Ordered CartesianTreeMap | Cartesian Tree | 75.40 | 39.86 | 40.16 | 8.13 | 73.72 |
| Zig | Ordered SkipListMap | Skip List | 76.06 | 49.33 | 49.58 | 3.02 | 68.36 |
| Zig | std.Treap (Map) | Treap | 56.76 | 30.65 | 34.14 | 9.10 | 64.49 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Insert Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 296
    bar [66.18, 79.12, 97.43, 41.78, 52.40, 60.19, 71.83, 256.88, 84.04, 42.69, 58.12, 35.09, 75.40, 76.06, 56.76]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Hit Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 105
    bar [52.32, 43.72, 57.21, 22.05, 42.01, 37.60, 83.49, 91.27, 82.83, 28.26, 11.30, 19.34, 39.86, 49.33, 30.65]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Miss Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 91
    bar [57.34, 48.86, 57.31, 23.25, 41.17, 38.15, 72.71, 52.94, 78.44, 28.28, 10.60, 20.52, 40.16, 49.58, 34.14]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Iterate Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 83
    bar [1.61, 6.08, 2.53, 0.71, 0.26, 6.14, 41.50, 41.84, 71.63, 1.42, 0.29, 2.09, 8.13, 3.02, 9.10]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Maps Remove Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::map", "Java fastutil AVL", "Java fastutil RB", "Java TreeMap", "Rust std BTree", "Rust indexset", "Zig Ordered BTree", "Zig Cartesian", "Zig SkipList", "Zig Treap Map"]
    y-axis "Time (ns/op)" 0 --> 359
    bar [67.14, 80.05, 107.50, 39.92, 53.72, 58.93, 114.67, 311.80, 106.68, 48.82, 41.33, 47.03, 73.72, 68.36, 64.49]
```

#### Sorted Sets

| Language | Implementation | Data Structure | Insert (ns/op) | Lookup Hit (ns/op) | Lookup Miss (ns/op) | Iterate (ns/op) | Remove (ns/op) |
|---|---|---|---|---|---|---|---|
| C | tidwall/btree.c | B-tree | 64.05 | 53.49 | 58.67 | 1.62 | 65.21 |
| C | Klib kavl | AVL Tree | 83.06 | 40.91 | 47.03 | 5.57 | 78.46 |
| C | Klib kbtree | B-tree | 90.29 | 54.30 | 52.88 | 2.38 | 101.79 |
| C++ | Abseil btree_set | B-tree | 37.93 | 26.99 | 26.89 | 0.60 | 41.57 |
| C++ | Boost flat_set | Flat Sorted Vector | 43.81 | 42.55 | 42.71 | **0.15** | 44.72 |
| C++ | std::set | Red-Black Tree | 45.28 | 35.71 | 33.71 | 5.04 | 55.30 |
| Java | fastutil AVLTreeSet | AVL Tree (primitive long) | 81.30 | 64.58 | 73.77 | 43.02 | 106.52 |
| Java | fastutil RBTreeSet | Red-Black Tree (primitive long) | 169.50 | 59.57 | 67.39 | 43.32 | 185.88 |
| Java | java.util.TreeSet | Red-Black Tree (boxed Long) | 134.86 | 106.23 | 94.39 | 55.90 | 144.29 |
| Rust | std::collections::BTreeSet | B-tree | 38.38 | 29.55 | 29.45 | 1.47 | 41.93 |
| Rust | indexset::BTreeSet | Two-Level B-tree | **34.18** | **11.25** | **11.27** | 0.28 | **37.89** |
| Zig | Ordered RedBlackTreeSet | Red-Black Tree | 62.78 | 41.85 | 47.30 | 6.12 | 61.98 |
| Zig | Ordered SortedSet | Sorted Vector | 37.15 | 36.92 | 43.71 | 0.23 | 46.67 |
| Zig | std.Treap (Set) | Treap | 57.90 | 32.24 | 34.66 | 7.35 | 61.58 |

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Insert Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 195
    bar [64.05, 83.06, 90.29, 37.93, 43.81, 45.28, 81.30, 169.50, 134.86, 38.38, 34.18, 62.78, 37.15, 57.90]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Hit Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 123
    bar [53.49, 40.91, 54.30, 26.99, 42.55, 35.71, 64.58, 59.57, 106.23, 29.55, 11.25, 41.85, 36.92, 32.24]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Miss Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 109
    bar [58.67, 47.03, 52.88, 26.89, 42.71, 33.71, 73.77, 67.39, 94.39, 29.45, 11.27, 47.30, 43.71, 34.66]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Iterate Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 65
    bar [1.62, 5.57, 2.38, 0.60, 0.15, 5.04, 43.02, 43.32, 55.90, 1.47, 0.28, 6.12, 0.23, 7.35]
```

```mermaid
%%{init: {"xyChart": {"width": 900, "height": 650, "xAxis": {"labelRotation": 90, "labelPadding": 16}}}}%%
xychart-beta
    title "Sorted Sets Remove Latency (N = 1,000, Shuffled Keys, Seed 2026)"
    x-axis ["C tidwall btree", "C Klib kavl", "C Klib kbtree", "C++ Abseil BTree", "C++ Boost flat", "C++ std::set", "Java fastutil AVL", "Java fastutil RB", "Java TreeSet", "Rust std BTree", "Rust indexset", "Zig RedBlack", "Zig SortedSet", "Zig Treap Set"]
    y-axis "Time (ns/op)" 0 --> 214
    bar [65.21, 78.46, 101.79, 41.57, 44.72, 55.30, 106.52, 185.88, 144.29, 41.93, 37.89, 61.98, 46.67, 61.58]
```