A data structure for optimistic concurrency control on ranges of bitwise-lexicographically-ordered keys.

Intended as an alternative to FoundationDB's skip list.

Hardware for all benchmarks is an AMD Ryzen 9 7900 with (2x32GB) 5600MT/s CL28-34-34-89 1.35V RAM.

```
$ clang++ --version

Ubuntu clang version 21.1.8 (6ubuntu1)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/lib/llvm-21/bin
```

# Microbenchmark

## Skip list

|               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|              171.37 |        5,835,467.28 |    0.5% |        2,915.46 |          629.31 |  4.633 |         502.91 |    0.0% |      0.01 | `point reads`
|              168.16 |        5,946,774.62 |    0.5% |        2,859.73 |          619.03 |  4.620 |         488.59 |    0.0% |      0.01 | `prefix reads`
|              245.86 |        4,067,294.63 |    0.3% |        3,508.97 |          904.82 |  3.878 |         627.73 |    0.0% |      0.01 | `range reads`
|              381.14 |        2,623,691.76 |    0.2% |        5,127.16 |        1,402.60 |  3.655 |         830.59 |    1.7% |      0.01 | `point writes`
|              376.24 |        2,657,887.07 |    0.3% |        5,062.85 |        1,381.07 |  3.666 |         811.68 |    1.6% |      0.01 | `prefix writes`
|              257.09 |        3,889,688.44 |    3.8% |        3,010.09 |          949.42 |  3.170 |         521.34 |    2.9% |      0.01 | `range writes`
|              629.71 |        1,588,026.28 |    4.0% |        6,809.60 |        2,320.32 |  2.935 |       1,247.08 |    1.3% |      0.01 | `monotonic increasing point writes`
|          126,164.50 |            7,926.16 |    1.7% |      772,460.25 |      463,264.67 |  1.667 |     141,512.00 |    0.2% |      0.01 | `worst case for radix tree`
|               15.33 |       65,217,669.23 |    0.4% |          299.00 |           56.45 |  5.297 |          64.00 |    0.0% |      0.01 | `create and destroy`

## Radix tree (this implementation)


|               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|               12.81 |       78,088,759.03 |    0.7% |          187.38 |           47.15 |  3.974 |          33.70 |    0.5% |      0.01 | `point reads`
|               16.77 |       59,626,501.14 |    0.4% |          277.61 |           61.74 |  4.497 |          44.76 |    0.4% |      0.01 | `prefix reads`
|               42.45 |       23,556,818.87 |    0.4% |          856.96 |          156.09 |  5.490 |         126.22 |    0.2% |      0.01 | `range reads`
|               15.76 |       63,453,196.94 |    0.3% |          249.89 |           58.04 |  4.306 |          33.21 |    0.5% |      0.01 | `point writes`
|               29.71 |       33,662,499.39 |    0.1% |          509.14 |          109.33 |  4.657 |          70.26 |    0.5% |      0.01 | `prefix writes`
|               35.77 |       27,956,388.03 |    0.8% |          614.18 |          131.72 |  4.663 |          85.57 |    0.1% |      0.01 | `range writes`
|               80.13 |       12,480,456.47 |    1.5% |        1,279.04 |          294.90 |  4.337 |         234.68 |    0.1% |      0.01 | `monotonic increasing point writes`
|          360,748.00 |            2,772.02 |    2.6% |    4,401,835.00 |    1,318,754.00 |  3.338 |     728,537.00 |    0.0% |      0.01 | `worst case for radix tree`
|               90.69 |       11,027,103.45 |    1.0% |        1,686.00 |          333.80 |  5.051 |         284.00 |    0.0% |      0.01 | `create and destroy`

# "Real data" test

Point queries only. Gc ratio is the ratio of time spent doing garbage collection to time spent adding writes or doing garbage collection. Lower is better.

## skip list

```
Check: 4.42779 seconds, 368.253 MB/s, Add: 4.64942 seconds, 120.586 MB/s, Gc ratio: 28.8784%, Peak idle memory: 5.51735e+06
```

## radix tree

```
Check: 0.891163 seconds, 1829.69 MB/s, Add: 1.23064 seconds, 455.579 MB/s, Gc ratio: 42.9417%, Peak idle memory: 2.28333e+06
```

## hash table

(The hash table implementation doesn't work on range queries, and its purpose is to provide an idea of how fast point queries can be)

```
Check: 0.858484 seconds, 1899.33 MB/s, Add: 0.632886 seconds, 885.868 MB/s, Gc ratio: 41.252%, Peak idle memory: 0
```