nv-tree · research · also NVTree

NV-Tree

NV-Tree is a persistent B+ tree variant that preserves recoverable leaf state while allowing internal routing nodes to be reconstructed after a crash.

Publication order: Flush the new entry before advancing and flushing its atomic entry count; readers scan only that published prefix. [1]

Space: Deletes append cancellation entries; updates append cancellation and replacement entries, so deletion can temporarily consume leaf space. [1]

Recovery: Full leaf parents force normal-operation rebuilding. Crash recovery scans leaves; a clean restart can reuse internal nodes after a successful shutdown protocol. These are different recovery paths. [1]

Rebuilding share: Table 2 gives 19,164.135 ms / 692,341.866 ms = 2.77% for 100 million insertions with 512-byte nodes. This contradicts section 4.7's blanket below-1% claim. The denominator is total execution time, not crash-recovery latency. [1] [3]

Comparison: FPTree places inner nodes in DRAM, whereas the original NV-Tree assumes an NVM-only arrangement. The FPTree evaluation also moves its reimplemented NV-Tree's inner nodes into DRAM; its results are not measurements of the unchanged FAST 2015 configuration. [2]

Relations

related
FPTree, B+ tree

Limitations

  • The FAST 2015 measurements use an NVDIMM server. They do not establish performance on every persistent-memory technology or modern platform. [1]
  • FPTree's authors identify persistent allocation leaks as a limitation of NV-Tree's design. Recovering tree contents is not, by itself, evidence that every allocation is reclaimed. [2]

Citations

  1. Yang, Wei, Chen, Wang, Yong and He. NV-Tree: Reducing Consistency Cost for NVM-based Single Level Systems. FAST 2015, pp. 167-181; sections 3.2 and 4.2. (accessed 2026-11-15)
  2. Oukid et al. FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory. SIGMOD 2016; secs. 2-4 and 6.1. DOI: 10.1145/2882903.2915251. (accessed 2026-11-15)
  3. Hesela: executable arithmetic for the FAST 2015 Table 2 rebuilding share, with source coordinates. (accessed 2026-11-15)
Sources & caveats
  • Source comparison and arithmetic on published aggregate times, not a native implementation, crash experiment or benchmark reproduction.
  • Interpretation: evaluate publication order, allocation recovery and restart work separately; a recoverable index is not a complete database durability contract.

JSON: /data/terms/nv-tree.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. NV-Tree. Hesela. 2026-11-15. https://hesela.dev/terms/nv-tree/