Tag
node-layout
- Jun 8, 2026 Adaptive Radix Tree Node Layouts ART keeps fan-out high without paying a 256-way node per prefix: four node widths, a 256-entry indirection table, path compression inside the header, and lazy expansion of leaves. data structures
- Apr 8, 2026 Child Representation and the Branching Factor Problem in Tries A trie costs one child lookup per key byte, so the node layout decides memory and speed. Compares dense arrays, sorted and linked child lists, bitmaps with rank, and double-array layouts. data structures
- Apr 22, 2025 Marking Key Boundaries in a Trie A trie node must distinguish a prefix from a stored key. The terminal marker costs one bit, one child slot, or one pointer depending on layout, and each choice changes lookup and iteration. data structures