A new index structure for non-volatile memory promises to cut the latency of long-key lookups in large-scale key-value stores by letting queries leap over the deepest layers of a radix tree instead of walking them byte by byte. The system, called HIACS, was described in a paper published on 8 September 2026 in the open-access journal Data Science and Engineering by Junbao Song, Derong Shen, Tiezheng Nie, Yue Kou and Jiarui Qi. In benchmarks on Intel Optane persistent memory under mixed YCSB workloads, HIACS outperformed mainstream NVM indexes including PACTree and LITS by 23 to 58 percent in throughput and improved 99th-percentile latency by more than 40 percent.
The motivation comes from a hardware mismatch that has long frustrated database engineers. Non-volatile memory offers nanosecond-level access latency and data persistence, which makes it attractive for indexes that must survive crashes without lengthy rebuilds. But NVM writes are expensive: a 64-byte cache-line write on Optane-class media can trigger a 256-byte read-modify-write operation at the XPLine level, producing severe write amplification. Bandwidth is also limited and can saturate under heavy multi-threading. For pointer-chasing index traversals, which issue dependent reads one after another, these characteristics are especially punishing.
The Adaptive Radix Tree, or ART, is a natural candidate for such systems because it handles variable-length keys efficiently through prefix compression and adaptive node layouts, and it avoids the rebalancing costs of B+ trees. The problem is depth. ART traverses a trie character by character, so its read path grows with key length. The paper’s own analysis shows that for string-like keys with small effective alphabets, ART becomes substantially deeper than a page-oriented B+ tree at scale: at 10^6 keys or more, ART’s average lookup depth exceeds the B+ tree’s by more than 50 percent, and the gap can reach multiple folds for keys built from a fixed prefix plus digits. On persistent memory, each extra level means another dependent cache-line fetch, so long keys translate directly into long waits.
Previous persistent ART designs, such as WORT and PACTree, reduced write amplification and ensured crash consistency by redesigning node layouts or decoupling leaf data, but they kept the original traverse-from-root search path. Learned indexes like LITS attempt to accelerate lookups with models, but the authors argue that model maintenance and runtime decision logic introduce overheads that can offset the read benefits under write-intensive workloads. The gap, as the paper frames it, is that existing solutions optimize how a node is accessed on NVM but not how many nodes must be accessed.
HIACS attacks that gap with a hybrid design. The primary index is an NVM-optimized ART, inheriting persistence-friendly choices from PACTree, including a B+ tree-style data layer with bidirectional leaf links and immutable anchor keys. The secondary index is the novel element: a Prefix Hash Adjacency List, dubbed the H-Skip List, which replaces the probabilistic skip pointers of a traditional skip list with a two-stage, hash-based directory. The first hash table maps a fixed-length key prefix to a candidate region; the second maps the suffix to a concrete ART node pointer, enabling a cross-level jump that lands near the target while preserving correct branch localization. A traditional skip list, relying on random level generation and full-key comparisons, cannot reliably localize an ART branch from partial key information, which is why the authors had to build a prefix-aware replacement.
Writes are handled by an asynchronous weak-consistency strategy. Leaf updates are persisted immediately, but structural modification operations such as node splits are logged and batch-applied by a background thread, and H-Skip List maintenance is likewise deferred. Every directory entry carries a version number matched to the ART node’s split version; a path is considered valid if the versions match or differ by no more than a threshold of three, which the authors found gave the best trade-off. Invalid paths are ignored and queries fall back to ordinary ART traversal, so correctness is preserved while the foreground path avoids synchronous cross-layer updates. The paper reports that this asynchronous design achieves 1.3 times the effective throughput of a synchronous update strategy in bandwidth-limited environments.
A third component, the dynamic monitoring module, tracks how many ART nodes sit at each level and uses a probability model, refined with a dynamic linear model and a key-length-based prediction, to choose the initial prefix length for H-Skip List queries. The authors report that the final key-value hierarchy prediction is accurate about 80 percent of the time and reduces H-Skip List query operations by about 30 percent. The module also adjusts the threshold governing which ART levels get indexed, compressing the auxiliary structure when deep nodes become too numerous. Together, these mechanisms shorten the average search path by 18.7 percent while keeping total space consumption 10 percent below that of B+ trees.
The evaluation was run on a dual-socket server with Montage Jintide C6230R CPUs, 62 GB of DDR4 memory, and two 128 GB Intel Optane DCPMM modules in App Direct mode, using YCSB workloads with 8-byte integer keys and 256-byte values on average, against PACTree, PDL-ART, BzTree, LITS and FastFair. In read-intensive workloads, HIACS delivered 30 percent higher throughput than PDL-ART, attributed to the H-Skip List reducing ART’s vertical traversal steps by up to 67 percent. In the range-scan workload it beat PACTree by 28 percent, and in single-threaded tests it matched or exceeded the best baselines, outperforming them by up to 50 percent in Workload C. In write-intensive workloads its throughput was comparable to PACTree’s, with LITS trailing by 12 to 15 percent in those scenarios.
The design is not without costs, and the authors are explicit about them. Under write-intensive workloads such as Workload A, HIACS showed higher 99.99th-percentile latency than PACTree, because background maintenance competes with foreground operations for CPU cache and NVM bandwidth, and newly inserted keys may not yet appear in the auxiliary structure. The team measured a valid hit rate of about 81.9 percent for the H-Skip List under high write pressure, meaning 18.1 percent of queries paid a small failed-lookup cost, typically one or two cache-line accesses, before falling back to ART. The auxiliary index also raises memory consumption by 15 percent compared with using ART alone, though at 310 million keys HIACS still used about 40 GB, less than BzTree, with the H-Skip List accounting for 6.246 GiB, or 15.3 percent of the total 40.9 GiB footprint.
For practitioners, the results suggest that where indexes live on persistent memory and keys are long, shared-prefix strings such as URLs, file paths or user-generated identifiers, decoupling the logical key length from the physical access path can pay off in both average and tail latency, provided the workload can tolerate bounded staleness in an auxiliary structure. The authors note that future work will target extreme data skew and integration with transactional systems, and they caution that under sustained write bursts the acceleration path weakens gracefully rather than disappearing, recovering automatically once background maintenance catches up.
Subject of Research: A hybrid index structure combining an adaptive radix tree with a prefix-hash skip list to accelerate key-value lookups on non-volatile memory storage devices.
Article Title: HIACS: A High-Performance Hybrid Index Structure Combining ART and Skip List for Non- Volatile Memory Storage Devices
Article References: Song, J., Shen, D., Nie, T., Kou, Y., & Qi, J. (2026). HIACS: A High-Performance Hybrid Index Structure Combining ART and Skip List for Non- Volatile Memory Storage Devices. Data Science and Engineering. https://doi.org/10.1007/s41019-026-00356-8
Image Credits: AI Generated
DOI: 10.1007/s41019-026-00356-8
Keywords: non-volatile memory, persistent memory, index structures, adaptive radix tree, skip list, key-value stores, write amplification, H-Skip List, YCSB benchmarks, Intel Optane, tail latency, database systems
News Source: Denise Maddox. (October 28, 2026). Hybrid Index Speeds Deep Key Lookups on Persistent Memory by Up to 58 Percent. Scienmag.
