CRT Database Index

5-dimensional perfect hash via CRT decomposition. O(1) lookup. O(1) range queries per channel. CC0.

How It Works

Every integer in Z/970200Z has a UNIQUE address in 5 dimensions:
  key -> (key mod 8, key mod 9, key mod 25, key mod 49, key mod 11)

This IS a perfect hash function — zero collisions by the Chinese Remainder Theorem.
No hash table resizing. No collision chains. No load factor tuning.

RANGE QUERIES: instead of scanning all records, query PER CHANNEL.
  "Find all keys where key mod 49 = 7" -> instant bucket lookup.
  Combine channel constraints with CRT -> exact key recovery.

MULTI-DIMENSIONAL: each CRT channel is an independent index dimension.
  Like having 5 B-trees for free, with algebraic relationships between them.

Insert: O(1). Lookup: O(1). Range query: O(bucket_size). Delete: O(1).
No rebalancing. No rehashing. The ring structure IS the index.

Insert Records

Records
0
Collisions
0 (impossible)
Load Factor
0%

Exact Lookup (O(1))

Channel Range Query

Find all records matching a constraint on ONE CRT channel.

Multi-Channel Query (CRT Intersection)

Constrain multiple channels simultaneously. CRT reconstructs the unique key.






Performance Comparison

Bucket Distribution

How records distribute across each channel's buckets.

CC0 1.0 Universal - No Rights Reserved. CRT-based database indexing using Z/970200Z = Z/8 x Z/9 x Z/25 x Z/49 x Z/11.
5-dimensional perfect hash. O(1) lookup. Per-channel range queries. No collisions. No rebalancing.
No patents. No dependencies. No permission needed. antonlebed.com