RadixForge 0.1.0-preview.1

RadixForge

A concurrent, mutable, multi-value adaptive radix index for .NET 10.

RadixForge turns strings, integers, bytes, and domain keys into a compact byte-oriented search tree for fast exact and prefix lookup. The name combines radix—the branching alphabet used by the index—with forge—the focus on a practical, production-engineered collection.

This is a .NET 10 library for fast exact and prefix indexing over strings, integers, raw bytes, and custom key types. It combines a path-compressed adaptive radix tree with production features that lightweight prefix maps usually omit:

• multiple values and duplicate values under one key;
• concurrent readers and writers;
• explicit removal by key and value;
• constant-time subtree counts after locating a prefix;
• allocation-free visitor queries in direct mode;
• stable snapshot results and lock-held lazy enumeration;
• direct and compactable buffered mutation modes;
• canonical codecs for ordinal strings and fixed-width integers;
• a public codec contract for application-specific keys.

The package is an in-memory secondary index, not a full-text search engine and not a replacement for every .NET collection.

Quick start

using RadixForge;

using var names = new RadixIndex<string, Person>(
    RadixKeyCodecs.Utf16Ordinal);

names.Add("Ernie", new Person(1, "Ernie"));
names.Add("Ernest", new Person(2, "Ernest"));
names.Add("Ernie", new Person(3, "Ernie"));

IReadOnlyList<Person> exact = names.FindExact("Ernie"); // two values
IReadOnlyList<Person> prefix = names.FindByPrefix("Er"); // three values
int count = names.CountByPrefix("Er");                  // no result list

var totalIds = 0;
names.VisitByPrefix("Er", person => totalIds += person.Id);

public sealed record Person(int Id, string Name);

The package targets .NET 10 only. Once the first public preview is published:

dotnet add package RadixForge --prerelease

Documentation

Start with the guide that matches what you are building:

The documentation index also provides a task-oriented route through all examples.

Why use it?

Use RadixIndex<TKey,TItem> when an application needs to maintain a live starts-with index rather than repeatedly scan a collection:

nameIndex.Remove(oldName, person);
nameIndex.Add(person.Name, person);

The index is particularly suited to database-like secondary indexes, command or route lookup, symbol tables, autocomplete candidate retrieval, hierarchical byte keys, and high-byte numeric partitions.

Choose a different structure when:

• lookup is exact-only and one value belongs to each key: use Dictionary or FrozenDictionary;
• data is immutable and sorted range scans dominate: use a sorted contiguous representation;
• queries require contains, fuzzy matching, tokenization, stemming, ranking, wildcards, or linguistic collation: use a search engine;
• numeric queries are arbitrary intervals rather than encoded high-byte partitions: use a range-oriented index.

Measured performance

The following results use 50,000 distinct ordinal string keys with one int per key on .NET 10.0.9. They compare the production RadixIndex API with the pinned NuGet packages PrefixLookup 0.1.17 and KTrie 3.0.1. Lower is better.

The radix visitor allocated no managed memory in either measured prefix workload. PrefixLookup remains about 21% faster for this exact one-value hit; Dictionary<string,int> measured 17.8 ns and remains the correct exact-only control. The production feature layers also make the radix slower than the minimal architecture prototype, which is why both sets of numbers remain in the repository.

These measurements are not universal promises. Key distribution, result size, codec cost, value multiplicity, mutation pattern, CPU, runtime, and query API all matter. See PRODUCTION-BENCHMARKS.md for the methodology and reproduction commands.

Architecture

Keys are encoded into canonical bytes and stored in one path-compressed adaptive radix tree. A node stores a shared byte segment instead of one object per character. Child storage grows with actual fan-out:

0 children -> no child allocation
1..4       -> Node4
5..16      -> Node16
17..48     -> Node48
49..256    -> Node256

A one-value terminal stores its value inline. It allocates a value list only when a second value is added. Every node maintains its visible subtree value count, making CountExact and CountByPrefix independent of the number of returned values after the key path is found.

Path splitting, pruning, and merging are iterative. Very long keys and deeply shared paths do not rely on recursive mutation or compaction. Prefix visitors use pooled traversal storage and do not box per-node enumerators.

Typical costs are:

Built-in key codecs

RadixKeyCodecs supplies reusable, thread-safe codecs for:

• ordinal and ordinal-ignore-case .NET strings;
• byte[] and ReadOnlyMemory<byte>;
• byte, sbyte, and char;
• signed and unsigned 16-, 32-, and 64-bit integers.

using var ids = new RadixIndex<int, Customer>(RadixKeyCodecs.Int32);

ids.Add(-20, minusTwenty);
ids.Add(42, fortyTwo);

Customer result = ids.FindExact(42).Single();

Integer codecs flip the sign bit where required and write most-significant bytes first. Lexicographic encoded order therefore matches natural integer order. A numeric prefix is a high-byte partition, not a decimal-text prefix:

// Match values sharing the first encoded byte with zero.
int partitionCount = ids.CountByPrefix(0, encodedPrefixLength: 1);

// A zero-byte prefix visits the whole numeric index in encoded key order.
IReadOnlyList<Customer> all = ids.FindByPrefix(0, encodedPrefixLength: 0);

String correctness

RadixKeyCodecs.Utf16Ordinal writes each UTF-16 code unit big-endian. This is intentional:

• every possible .NET string, including unpaired surrogates, is preserved;
• byte equality equals StringComparison.Ordinal equality;
• byte ordering equals .NET ordinal UTF-16 ordering;
• a string prefix remains an encoded-byte prefix.

UTF-8 is not the default because strict UTF-8 cannot represent unpaired surrogates and its scalar ordering differs from UTF-16 ordinal ordering around the BMP/supplementary boundary.

Utf16OrdinalIgnoreCase uses the runtime-compatible ordinal equivalence model, including Greek sigma and supplementary-plane case pairs. It is not culture-sensitive search.

Custom key types

Implement IRadixKeyCodec<TKey> when a domain key has a stable binary form:

using System.Buffers.Binary;

public sealed class TenantDocumentCodec : IRadixKeyCodec<TenantDocumentKey>
{
    public int GetEncodedLength(TenantDocumentKey key) => 8;

    public int Encode(TenantDocumentKey key, Span<byte> destination)
    {
        BinaryPrimitives.WriteUInt32BigEndian(destination, key.TenantId);
        BinaryPrimitives.WriteUInt32BigEndian(destination[4..], key.DocumentId);
        return 8;
    }
}

public readonly record struct TenantDocumentKey(uint TenantId, uint DocumentId);

A codec must be deterministic and thread-safe, report its exact output length, and write exactly that many bytes. Equal application keys must have identical encodings. Prefix and ordering operations are meaningful only when the codec's byte layout preserves the relationship required by the application.

Multi-value and duplicate behavior

Add always adds one value. The same key/value pair may be added more than once. Remove(key, value) removes one visible match according to the supplied item equality comparer:

using var byEmail = new RadixIndex<string, Person>(
    RadixKeyCodecs.Utf16OrdinalIgnoreCase,
    itemEqualityComparer: PersonIdComparer.Instance);

The optional item comparer globally sorts snapshot results. Without one, terminal values preserve insertion order and prefix traversal follows encoded key order. Equality and ordering comparers must remain stable while values are indexed.

The index stores strong references to values. Index stable IDs instead of full objects when another store should own object lifetime.

Query APIs

Snapshots copy matching references under a read lock and remain valid after later mutation:

IReadOnlyList<TItem> FindExact(TKey key);
IReadOnlyList<TItem> FindByPrefix(TKey prefix);
IReadOnlyList<TItem> FindByPrefix(TKey key, int encodedPrefixLength);

Counts do not materialize results:

int CountExact(TKey key);
int CountByPrefix(TKey prefix);
int CountByPrefix(TKey key, int encodedPrefixLength);

Visitors avoid a result collection on the direct-mode fast path:

int VisitExact(TKey key, Action<TItem> visitor);
int VisitByPrefix(TKey prefix, Action<TItem> visitor);

With no item comparer, direct-mode visitors allocate no managed memory in the measured workloads. On that fast path, the callback runs under the read lock and must not mutate the same index. Buffered mode and a configured item comparer take a visible snapshot first, then invoke the callback after releasing the lock.

Lazy enumeration also holds a read lock until completion or disposal:

IEnumerable<TItem> EnumerateExact(TKey key);
IEnumerable<TItem> EnumerateByPrefix(TKey prefix);

Prefer snapshots for ordinary application code. Use visitors for hot aggregate paths and lazy enumeration only when the caller tightly controls enumerator lifetime.

Mutation modes

Direct mode is the RadixIndex default and applies writes immediately:

using var index = new RadixIndex<string, Person>(
    RadixKeyCodecs.Utf16Ordinal,
    new RadixIndexOptions { MutationMode = RadixIndexMutationMode.Direct });

Buffered mode maintains a main tree, addition overlay, and removal tombstones:

visible = main - removals + additions

using var buffered = new RadixIndex<string, Person>(
    RadixKeyCodecs.Utf16Ordinal,
    new RadixIndexOptions
    {
        MutationMode = RadixIndexMutationMode.Buffered,
        AutomaticCompactionThreshold = 20_000 // zero means explicit only
    });

RadixIndexCompactionResult compacted = buffered.Compact();

Buffered mode is useful when overlay behavior is desirable, but direct mode has lower steady-state complexity and does not retain tombstones. The default automatic threshold is 4,096 pending operations.

AddRange encodes its complete input before taking the write lock. An exception from source enumeration or encoding therefore does not leave a partial batch.

Concurrency and lifetime

One ReaderWriterLockSlim protects each index:

• counts, snapshots, visitors, and lazy queries take a read lock;
• add, remove, clear, and compaction take a write lock;
• returned values are not made immutable or thread-safe;
• codecs and comparers must be safe for the calling pattern.

Dispose is idempotent, clears strong references, and causes later operations to throw ObjectDisposedException. Do not dispose an index while a lazy enumerator is active.

Current release status

The release gate includes:

• 96 correctness, differential, stress, Unicode, long-key, codec, adaptive child-shape, mutation, snapshot, disposal, and concurrency tests;
• full .NET 10 analyzers with warnings treated as errors;
• tracked public API, XML documentation, deterministic builds, symbols, and package validation;
• same-process BenchmarkDotNet comparisons and fresh-process retained-memory probes;
• local package inspection and clean-consumer smoke testing.

The package, assembly, solution, projects, namespace, tests, and benchmark identity are now consistently named RadixForge. RadixForge is available under the MIT License. Source and CI are hosted in the public ToolMaker/RadixForge repository. Every push is validated, while NuGet.org publication is intentionally limited to a published versioned GitHub Release. See RELEASE-CHECKLIST.md.