Computer Science

Computer Science ›› 2026, Vol. 53 ›› Issue (1): 77-88.doi: 10.11896/jsjkx.250200109

• Database & Big Data & Data Science • Previous Articles     Next Articles

Survey on Optimization B+ Tree Index for Persistent Memory

LU Chao, YANG Chaoshu, YAO Zhengzhu, LIU Ying, ZHANG Runyu   

  1. College of Computer Science and Technology, Guizhou University, Guiyang 550025, China;
    State Key Laboratory of Public Big Data, Guiyang 550025, China
  • Received:2025-02-26 Revised:2025-06-20 Published:2026-01-08
  • About author:LU Chao,born in 2001,master.His main research interest is persistent memory indexing.
    ZHANG Runyu,born in 1995,Ph.D,associate professor,master supervisor,is a member of CCF(No.L9886M).His main research interests include non-volatile memories and storage systems.
  • Supported by:
    Fund for Less Developed Regions of the National Natural Science Foundation of China(62162011,62362009) and Talent Introduction Project of Guizhou University([2022]44).

PDF (PC)

4

Abstract: The advent of persistent memory(PM) introduces new perspectives for index structure design while presenting challenges in data consistency,persistence overhead,and concurrency control.As a widely adopted index structure in storage systems,the B+ tree requires tailored adaptations to harness PM’s unique features,including byte-addressability,non-volatility,and low latency.This paper focuses on the optimization of B+ tree indexes for persistent memory,beginning with an analysis of the challenges in designing PM-based B+ trees.Then,optimization strategies are reviewed from two perspectives:PM-only architectures and DRAM-PM hybrid architectures.For PM-only architectures,advancements in data consistency mechanisms,concurrency control optimizations,and innovative leaf node designs are summarized,with an emphasis on enhancing write operation efficiency while ensuring instant recovery.For DRAM-PM hybrid architectures,strategies based on leaf node structure optimization and auxiliary structure enhancement are examined,highlighting approaches to improve indexing performance through selective persis-tence.Finally,a detailed analysis of the design characteristics,advantages,and limitations of optimization schemes under both architectures is presented,offering insights into future research directions for B+ tree index optimization in these contexts.

Key words: Persistent memory, B+ Tree, Read-write optimization, Data consistency, Persistence overhead

CLC Number: 

  • TP311
[1]ZHANG H,ANDERSEN D G,PAVLO A,et al.Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes[C]//Proceedings of the 2016 International Confe-rence on Management of Data.ACM,2016:1567-1581.
[2]ZHANG M Z,ZHANG F,LIU Z Y.A Survey on Architecture Research of Novel Non-Volatile Memory Based on Dynamical Trade-Off[J].Journal of Computer Research and Development,2019,56(4):677-691.
[3]SHEN Z R,XUE W,SHU J W.Research on New Non-Volatile Storage[J].Journal of Computer Research and Development,2014,51(2):445-453.
[4]HELLENBRAND M,TECK I,MACMANUS-DRISCOLL J L.Progress of Emerging Non-Volatile Memory Technologies in Industry[J].MRS Communications,2024,14:1099-1112.
[5]SHU J W,LU Y Y,ZHANG J C,et al.Research progress on non-volatile memory based storage system[J].Science & Technology Review,2016,34(14):86-94.
[6]HE Y X,SHEN F F,ZHANG J,et al.Cache Optimization Approaches of Emerging Non-Volatile Memory Architecture:A Survey[J].Journal of Computer Research and Development,2015,52(6):1225-1241.
[7]QURESHI M K,SRINIVASAN V,RIVERS J A.Scalable high performance main memory system using phase-change memory technology[C]//Proceedings of the 36th Annual International Symposium on Computer Architecture.New York:ACM,2009:24-33.
[8]WU Z L,JIN P Q,YUE L H,et al.A Survey on PCM-Based Big Data Storage and Management[J].Journal of Computer Research and Development,2015,52(2):343-361.
[9]MAO W,LIU J N,TONG W,et al.A Review of Storage Technology Research Based on Phase Change Memory[J].Journal of Computer Science and Technology,2015,38(5):944-906.
[10]BEDESCHI F,RESTA C,KHOURI O,et al.An 8Mb demonstrator for high-density 1.8V Phase-Change Memories[C]//2004 Symposium on VLSI Circuits.IEEE,2004:442-445.
[11]MANOHAR S S,KAPOOR H K.CAPMIG:Coherence-Aware Block Placement and Migration in Multiretention STT-RAM Caches[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2023,42(2):411-422.
[12]GAJARIA D,ADEGBIJA T.Evaluating the Performance andEnergy of STT-RAM Caches for Real-World Wearable Workloads[J].Future Generation Computer Systems,2022,136:231-240.
[13]SADRI-MOSHKENANI P,KHAN M W,ISLAM M S,et al.Optoelectronic Readout of STT-RAM Based on Plasmon Drag Effect[J].IEEE Journal of Quantum Electronics,2021,57(6):1-7.
[14]HUNG J M,WEN T H,HUANG Y H,et al.8-b Precision 8-Mb ReRAM Compute-in-Memory Macro Using Direct-Current-Free Time-Domain Readout Scheme for AI Edge Devices[J].IEEE Journal of Solid-State Circuits,2023,58(1):303-315.
[15]LI W,WANG Y,LIU C,et al.On-Line Fault Protection for ReRAM-Based Neural Networks[J].IEEE Transactions on Computers,2023,72(2):423-437.
[16]YANG J,LUO Q,XUE X,et al.A 9Mb HZO-Based EmbeddedFeRAM with 10 12 -Cycle Endurance and 5/7ns Read/Write using ECC-Assisted Data Refresh and Offset-Canceled Sense Amplifier[C]//2023 IEEE International Solid- State Circuits Conference(ISSCC).IEEE,2023:1-3.
[17]LUO Y,LUC Y C,YU S.AFeRAM based Volatile/Non-Volatile Dual-Mode Buffer Memory for Deep Neural Network Trai-ning[C]//2021 Design,Automation & Test in Europe Confe-rence & Exhibition(DATE).IEEE,2021:1871-1876.
[18]IZRAELEVITZ J,YANG J,ZHANG L,et al.Basic Perfor-mance Measurements of the Intel Optane DC Persistent Memory Module[J].arXiv:1903.05714,2019.
[19]YANG J,LI B,LILJA D J.Exploring Performance Characteristics of the Optane 3DXpoint Storage Technology[J].ACM Transactions on Modeling and Performance Evaluation of Computing Systems,2020,5(1):1-28.
[20]GUGNANI S,KASHYAP A,LU X.Understanding the idiosyncrasies of real persistent memory[C]//Proceedings of the VLDB Endowment.2020:626-639.
[21]CHEN S,JIN Q.Persistent B+-trees in Non-Volatile MainMemory[C]//Proceedings of the VLDB Endowment.2015:786-797.
[22]HWANG D,KIM W H,WON Y,et al.Endurable transient inconsistency in Byte-Addressable persistent B+-Tree[C]//16th USENIX Conference on File and Storage Technologies(FAST 18).Oakland:USENIX Association,2018:187-200.
[23]YOO J,CHA H,KIM W,et al.Pivotal B+tree for Byte-Addressable Persistent Memory[J].IEEE Access,2022,10:46725-46737.
[24]LI T,WANG H,SHAO A,et al.SSB-Tree:Making Persistent Memory B+-Trees Crash-Consistent and Concurrent by Lazy-Box[C]//2022 IEEE International Parallel and Distributed Processing Symposium(IPDPS).IEEE,2022:70-80.
[25]ARULRAJ J,LEVANDOSKI J,MINHAS U F,et al.Bztree:A High-Performance Latch-Free Range Index for Non-Volatile Memory[C]//Proceedings of the VLDB Endowment.2018:553-565.
[26]KIM W H,KRISHNAN R M,FU X,et al.PACTree:A High Performance Persistent Range Index Using PAC Guidelines[C]//Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles.ACM,2021:424-439.
[27]HE X,ZHANG R,TIAN P,et al.WOPE:A Write-Optimized and Parallel-Efficient B+-Tree for Persistent Memory[J].Journal of Systems Architecture,2024,153:103187.
[28]MA R X,WU F,DONG B R,et al.Write-Optimized B+ Tree Index Technology for Persistent Memory[J].Journal of Computer Science and Technology,2021,36(5):1037-1050.
[29]WANG C,CHATTOPADHYAY S.Isle-Tree:A B+-Tree with Intra-Cache Line Sorted Leaves for Non-Volatile Memory[C]//2020 IEEE 38th International Conference on Computer Design(ICCD).IEEE,2020:573-580.
[30]LUO Y,JIN P,ZHANG Q,et al.TLBtree:A Read/Write-Optimized Tree Index for Non-Volatile Memory[C]//2021 IEEE 37th International Conference on Data Engineering(ICDE).IEEE,2021:1889-1894.
[31]WANG C,BRIHADISWARN G,JIANG X,et al.Circ-Tree:AB+-Tree Variantwith Circular Design for Persistent Memory[J].IEEE Transactions on Computers,2022,71(2):296-308.
[32]YAN W,ZHANG X J.A Concise Concurrent B+ -Tree for Persistent Memory[J].ACM Transactions on Architecture and Code Optimization,2024,21(2):1-25.
[33]YANG J,WEI Q,CHEN C,et al.NV-Tree:Reducing Consistency Cost for NVM-based Single Level Systems[C]//13th USENIX Conference on File and Storage Technologies(FAST 15).USENIX Association,2015:167-181.
[34]OUKID I,LASPERAS J,NICA A,et al.FPTree:AHybridSCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory[C]//Proceedings of the 2016 International Conference on Management of Data.ACM,2016:371-386.
[35]LIU J,CHEN S,WANG L.LB+Trees:Optimizing Persistent Index Performance on 3DXPoint Memory[C]//Proceedings of the VLDB Endowment.2020:1078-1090.
[36]WANG C,CHATTOPADHYAY S,BRIHADISWARN G.Crab-tree:A Crash Recoverable B+-tree Variant for Persistent Memory with ARMv8 Architecture[J].ACM Transactions on Embedded Computing Systems,2020,19(5):1-26.
[37]CHEN Y,LU Y,FANG K,et al.uTree:a Persistent B+-tree with Low Tail Latency[C]//Proceedings of the VLDB Endowment.2020:2634-2648.
[38]ZOU X,WANG F,FENG D,et al.ROWE-tree:A Read-Opti-mized and Write-Efficient B+-tree for Persistent Memory[C]//Proceedings of the 51st International Conference on Parallel Processing.ACM,2022:1-11.
[39]YAN W,ZHANG X J.A highly write-optimized concurrentB+-tree for persistent memory[J].Future Generation Computer Systems,2024,155:219-230.
[40]ZHOU X,SHOU L,CHEN K,et al.DPTree:Differential Indexing for Persistent Memory[C]//Proceedings of the VLDB Endowment.2019:421-434.
[41]ZHOU Y,SHENG T,WAN J.HBTree:an Efficient IndexStructure Based on Hybrid DRAM-NVM[C]//2021 IEEE 10th Non-Volatile Memory Systems and Applications Symposium(NVMSA).IEEE,2021:1-6.
[42]LI Z,HE S,DANG Z,et al.CCL-BTree:A Crash-Consistent Locality-Aware B+-Tree for Reducing XPBuffer-Induced Write Amplification in Persistent Memory[C]//Proceedings of the Nineteenth European Conference on Computer Systems.ACM,2024:441-455.
[43]STONEBRAKER M.The Design of The Postgres Storage Sys-tem[M].San Francisco:Morgan Kaufmann Publishers Inc.,1987:1-19.
[44]KIESEBERG P,SCHRITTWIESER S,FRUHWIRT P,et al.Analysis of the Internals of MySQL/InnoDB B+ Tree Index Navigation from a Forensic Perspective[C]//2019 International Conference on Software Security and Assurance(ICSSA).IEEE,2019:46-51.
[45]RODEH O,BACIK J,MASON C.BTRFS:The Linux B-Tree Filesystem[J].ACM Transactions on Storage,2013,9(3):1-32.
[46]SWEENEY A,DOUCETTE D,HU W,et al.Scalability in theXFS File System[C]//Proceedings of the 1996 Annual Conference on USENIX Annual Technical Conference.USENIX Association,1996:1-15.
[47]YANG C S,ZHUGE Q F,SHA X M,et al.Wear Attacks and Defense Mechanisms for Persistent In-memory File Systems[J].Journal of Software,2020,31(6):1909-1929.
[48]ZHANG R,LIU D,CHEN X,et al.ELOFS:An ExtensibleLow-Overhead Flash File System for Resource-Scarce Embedded Devices[J].IEEE Transactions on Computers,2022,71(9):2327-2340.
[49]YANG C,LIU D,CHEN X,et al.ReducingWrite Amplification for Inodes of Journaling File System using Persistent Memory[C]//2019 Design,Automation & Test in Europe Conference & Exhibition(DATE).IEEE,2019:866-871.
[50]KIM D,LEE J,LIM K S,et al.An LSM Tree Augmented with B+ Tree on Nonvolatile Memory[J].ACM Transactions on Storage,2024,20(1):1-24.
[51]XIA F,JIANG D,XIONG J,et al.HiKV:a Hybrid Index Key-Value Store for DRAM-NVM Memory Systems[C]//Proceedings of the 2017 USENIX Annual Technical Conference.USENIX Association,2017:349-362.
[52]LEPERS B,BALMAU O,GUPTA K,et al.KVell:the Design and Implementation of a Fast Persistent Key-Value Store[C]//Proceedings of the 27th ACM Symposium on Operating Systems Principles.ACM,2019:447-461.
[53]LIUB,YE Z,HU Q,et al.HPDK:A Hybrid PM-DRAM Key-Value Store for High I/O Throughput[J].IEEE Transactions on Computers,2024,73(6):1575-1587.
[54]KAIYRAKHMET O,LEE S,NAM B,et al.SLM-DB:Single-Level Key-Value Store with Persistent Memory[C]//Proceedings of the 17th USENIX conference on File and Storage Technologies(FAST 19).USENIX Association,2019:191-205.
[55]CHEN Y,LU Y,YANG F,et al.FlatStore:An Efficient Log-Structured Key-Value Storage Engine for Persistent Memory[C]//Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems.ACM,2020:1077-1091.
[56]WANG Z,SHOU L,CHEN K,et al.BushStore:Efficient B+Tree Group Indexing for LSM-Tree in Non-Volatile Memory[C]//2024 IEEE 40th International Conference on Data Engineering(ICDE).IEEE,2024:4127-4139.
[57]HAN X,TUCK J,AWAD A.Dolos:Improving thePerformance of Persistent Applications in ADR-Supported Secure Memory[C]//MICRO-54:54th Annual IEEE/ACM International Symposium on Microarchitecture.ACM,2021:1241-1253.
[58]ZHOU T,DU Y,YANG F,et al.EfficientAtomic Durability on eADR-enabled Persistent Memory[C]//Proceedings of the International Conference on Parallel Architectures and Compilation Techniques.ACM,2022:124-134.
[59]Intel.eADR:New Opportunities for Persistent Memory Applications [EB/OL].https://www.intel.com/content/www/us/en/developer/articles/technical/eadr-new-opportunities-for-persistent-memory-applications.html.
[60]MIN C,KIM K,CHO H,et al.SFS:random write consideredharmful in solid state drives[C]//Proceedings of the 10th USENIX conference on File and Storage Technologies(FAST 12).USENIX Association,2012:1-16.
[61]VOLOS H,TACK A J,SWIFT M M.Mnemosyne:Lightweight persistent memory[J].ACM SIGARCH Computer Architecture News,2011,39(1):91-104.
[62]CONDIT J,NIGHTINGALE E B,FROST C,et al.Better I/OThrough Byte-Addressable,Persistent Memory[C]//Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles.ACM,2009:133-146.
[63]OWENS S,SARKAR S,SEWELL P.ABetter x86 MemoryModel:x86-TSO [C]//Theorem Proving in Higher Order Logi-cs,22nd International Conference,TPHOLs 2009.Springer,2009:391-407.
[64]SEWELL P,SARKAR S,OWENS S,et al.x86-TSO:A Rigo-rous and Usable Programmer’s Model for x86 Multiprocessors[J].Communications of the ACM,2010,53(7):89-97.
[65]WANG T,LEVANDOSKI J,LARSON P A.Easy Lock-Free Indexing in Non-Volatile Memory[C]//2018 IEEE 34th International Conference on Data Engineering(ICDE).IEEE,2018:461-472.
[66]LEIS V,KEMPER A,NEUMANN T.The Adaptive RadixTree:ARTful Indexing for Main-Memory Databases[C]//2013 IEEE 29th International Conference on Data Engineering(ICDE).IEEE,2013:38-49.
[67]LEIS V,SCHEIBNER F,KEMPER A,et al.The ART of Practical Synchronization[C]//Proceedings of the 12th International Workshop on Data Management on New Hardware.ACM,2016:1-8.
[68]CHEN S,GIBBONS P B,NATH S.Rethinking Database Algorithms for Phase Change Memory[C]//Proceedings of the Fifth Biennial Conference on Innovative Data Systems Research(CIDR).CIDR,2011:21-31.
[69]YANG J,KIM J,HOSEINZADEH M,et al.AnEmpirical Guide to the Behavior and Use of Scalable Persistent Memory[C]//18th USENIX Conference on File and Storage Technologies(FAST 20).USENIX Association,2020:169-182.
[70]WANG Z,LIU X,YANG J,et al.Characterizing and Modeling Non-Volatile Memory Systems[C]//2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture(MICRO).IEEE,2020:496-508.
[71]LIU J,CHEN S.Initial Experience with 3DXPoint Main Memory[C]//2019 IEEE 35th International Conference on Data Engineering Workshops(ICDEW).IEEE,2019:300-305.
[72]VENKATARAMAN S,TOLIA N,RANGANATHAN P,et al.Consistent andDurable Data Structures for Non-Volatile Byte-Addressable Memory[C]//9th USENIX Conference on File and Storage Technologies(FAST 11).USENIX Association,2011:61-75.
[73]LIU Y,LI H,CHENG Y,et al.CacheGen:KV Cache Compression and Streaming for Fast Large Language Model Serving[C]//Proceedings of the ACM SIGCOMM 2024 Conference.ACM,2024:38-56.
[1] ZUO Shun, LI Yongkun, XU Yinlong. Study on Collaborative Data Persistence in NewSQL Databases [J]. Computer Science, 2025, 52(1): 131-141.
[2] YANG Fan. Collision Detection Algorithm of AABB Bounding Box Based on B+ Tree [J]. Computer Science, 2021, 48(6A): 331-333.
[3] HOU Ze-yi, WAN Hu, XU Yuan-chao. NMST:A Persistent Memory Management Optimization Approach Based on Segment Tree [J]. Computer Science, 2018, 45(7): 78-83.
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs [J]. Computer Science, 2018, 45(3): 311-316.
[5] SUN Zhi-long, Edwin H-M Sha, ZHUGE Qing-feng, CHEN Xian-zhang and WU Kai-jie. Research on Data Consistency for In-memory File Systems [J]. Computer Science, 2017, 44(2): 222-227.
[6] XIONG Zhong-min, ZHU Ji-guang, LI Chang-ji and YUAN Hong-chun. Confluence Decision Method for Active Rule Set Based on Condition Conflict Analysis [J]. Computer Science, 2016, 43(5): 169-173.
[7] . Data Consistency Trust Evaluation of Wireless Sensor Networks Based on Multi-event Concurrent [J]. Computer Science, 2013, 40(3): 163-166.
[8] LIU Lin,XIONG Qi,WU Shi-zhong. Survey of Data Consistency Insurance Technologies for Continuous Data Protection [J]. Computer Science, 2011, 38(Z10): 124-127.
[9] . [J]. Computer Science, 2009, 36(4): 172-174.
[10] . [J]. Computer Science, 2007, 34(12): 111-113.
[11] . [J]. Computer Science, 2006, 33(4): 137-140.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.