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
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
- 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.
- 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.
- Hesela: executable arithmetic for the FAST 2015 Table 2 rebuilding share, with source coordinates.
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.