RadixForge 1.1.0

RadixForge

Concurrent, mutable, performance-oriented secondary indexes for .NET 10.

RadixForge provides two complementary in-memory index families:

• RadixIndex<TKey,TItem> for exact, starts-with, and ordered range lookup;
• AdaptiveGramIndex<TItem> for exact ordinal contains/substring lookup.

The name combines radix—the branching alphabet behind the original index—with forge—the focus on practical, production-engineered collections.

The radix index turns strings, integers, bytes, and domain keys into a compact byte-oriented search tree. The substring index packs UTF-16 trigrams into 48-bit keys and adapts each posting between a sorted array and a managed bitmap. Together they provide production features that lightweight lookup 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;
• inclusive, exclusive, bounded, and unbounded ordered ranges;
• 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;
• verified ordinal substring search without tokenization or external dependencies;
• result limits, cancellation, and broad-query scan fallback;
• mutable substring overlays with bounded automatic compaction.

The package is an in-memory secondary-index library, not a ranked or linguistic full-text 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);

Literal substring search uses stable item identifiers and one searchable string per item:

using var descriptions = new AdaptiveGramIndex<int>();

descriptions.Upsert(101, "High-performance in-memory indexes");
descriptions.Upsert(102, "A compact radix tree");
descriptions.Compact();

IReadOnlyList<int> matches = descriptions.FindContaining("memory"); // [101]
int count = descriptions.CountContaining("index");

descriptions.Upsert(101, "Updated searchable text");
descriptions.Remove(102);

The package targets .NET 10 only:

dotnet add package RadixForge

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.

Use AdaptiveGramIndex<TItem> when a collection is large enough that repeated ordinal string.Contains scans dominate query time. It is designed for literal property values, filenames, identifiers, descriptions, logs, and other text where ranking and linguistic analysis are not required.

Choose a different structure when:

• lookup is exact-only and one value belongs to each key: use Dictionary or FrozenDictionary;
• data is immutable and range scans dominate: a packed sorted representation can provide lower memory and faster read-only traversal;
• queries require fuzzy matching, tokenization, stemming, ranking, wildcards, or linguistic collation: use a search engine;
• the codec cannot encode keys so lexicographic byte order matches the desired application order: use another ordered structure or write an order-preserving codec.

Measured performance

Radix exact and prefix index

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.

Adaptive ordinal substring index

On a separate 100,000-string .NET 10.0.9 workload, the production CountContaining path measured:

Needles shorter than three UTF-16 code units deliberately scan. Dense trigram candidates also fall back to a scan rather than paying for an unhelpful posting intersection. Candidate verification always uses StringComparison.Ordinal, so the index does not trade correctness for speed. See the complete substring benchmark record.

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.

Ordered range queries are part of the production API; see the range guide. The supporting architecture research is documented in RANGE-INDEX-POC.md, and the production-shaped InterfaceDB selection work is in INTERFACEDB-RANGE-MANAGER-POC.md. The contains-index architecture and package benchmark are documented in SUBSTRING-INDEX-BENCHMARKS.md.

Architecture

RadixIndex and AdaptiveGramIndex share lifecycle goals but use different structures for different query shapes.

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:

The substring index instead builds immutable trigram posting segments. Sparse grams use sorted local document slots; dense grams use managed bitmap words. Pending upserts and tombstones form a bounded overlay until compaction. See the substring architecture guide for its query and mutation flow.

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:

• 137 correctness, differential, stress, Unicode, long-key, codec, adaptive child-shape, substring, 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.