As DRAM and other transistor-based memory technologies approach their scalability limits, alternative storage solutions like Phase-Change Memory (PCM) are gaining attention for their scalability, fast access times, and zero leakage power. However, current memory-intensive algorithms, especially those used in big data systems, often overlook PCM's endurance limitations (10^6 to 10^8 writes before degradation) and write asymmetry. Self-balancing binary search trees (BSTs), which are widely used for large-scale data management, were developed without considering PCM's unique properties, leading to potential performance degradation. This paper introduces HART, a novel hybrid addressing scheme for self-balancing BSTs, designed to optimize PCM's characteristics. By combining DFATGray code addressing for deeper nodes with linear addressing for shallower nodes, HART balances reduced bit flips during frequent rotations at deeper levels with computational simplicity at shallow levels. Experimental results on PCM-aware AVL trees demonstrate significant improvements in performance, with a reduction in bit flips leading to enhanced endurance, increased lifetime, and lower write energy and latency. Notably, these benefits are achieved without imposing substantial computational overhead, making HART an efficient solution for big data applications.

翻译：随着DRAM及其他基于晶体管的存储器技术逐渐接近其可扩展性极限，相变存储器等替代性存储解决方案因其可扩展性、快速访问时间和零泄漏功耗而受到关注。然而，当前内存密集型算法，特别是大数据系统中使用的算法，往往忽视了PCM的耐久性限制（退化前可写入10^6至10^8次）和写入不对称性。自平衡二叉搜索树作为大规模数据管理中广泛使用的数据结构，其设计未考虑PCM的独特特性，可能导致性能下降。本文提出HART，一种面向自平衡BST的新型混合寻址方案，旨在优化PCM的特性。该方案通过结合深层节点的DFATGray码寻址与浅层节点的线性寻址，在深层频繁旋转时减少比特翻转，同时在浅层保持计算简洁性。基于PCM感知的AVL树的实验结果表明，该方案显著提升了性能：比特翻转的减少增强了耐久性、延长了寿命，并降低了写入能耗与延迟。值得注意的是，这些优势的实现在未引入显著计算开销的前提下完成，使得HART成为大数据应用的高效解决方案。