CRT Database Index

Oracle/IBM patents. CC0 alternative.

CRT approach to database indexing. A key mod 7 coprime moduli gives 7 independent bucket addresses. Lookup = 7 mod operations. Insert = 7 bucket writes. Zero false positives for distinct keys within the ring. 132 total buckets address 214,414,200 unique keys.

How It Works

CRT Perfect Hash
A key k in Z/214,414,200 maps to 7 residues: (k mod 8, k mod 9, k mod 25, k mod 49, k mod 11, k mod 13, k mod 17). By CRT, this 7-tuple uniquely determines k. Store data at the intersection of 7 buckets. Lookup: compute 7 remainders, read 7 buckets, intersect. 3 data channels {mod 8, mod 25, mod 49} hold data pointers. 4 parity channels {mod 9, mod 11, mod 13, mod 17} hold integrity metadata.
O(1) lookup
7 mod + 7 reads
Constant time regardless of table size. No tree traversal.
132 buckets
Sum of moduli
8+9+25+49+11+13+17 = 132 buckets address 214.4M unique keys.
Perfect hash
CRT bijectivity
Distinct keys in ring always differ in at least one channel.
3+4 split
Data + integrity
3 data channels store pointers. 4 parity channels verify correctness.

Try It

Key (0-214414199):

Shows 7 bucket addresses for the key. Red = data channels. Green = parity channels.

Collision Test

CRT Index vs B-Tree/Hash Table

LookupB-tree: O(log N). Hash: O(1) amortizedCRT: O(1) worst-case. 7 mod ops.CollisionsHash tables: requires chaining/probingCRT: zero false positives within ringStorageB-tree: node overhead. Hash: load factor wasteCRT: 132 buckets total. Minimal.IntegritySeparate checksums needed4 parity channels (mod 9, 11, 13, 17) verify for free.Patent statusOracle/IBM database patentsCC0. Public domain. Forever.

Source code · Public domain (CC0)

Report issue

.ax source compiled to WASM via self-hosting compiler. Zero HTML authored.