EUVIMEDEUVIMED entdecken
Crossref

pTree: Building Efficient B+-Tree on Non-Volatile Memory With Processing-in-Memory

Yibo Liu, Bing Wu, Shiyi Song, Xueliang Wei, Huan Cheng, Heng Zhou, Wei Tong, Dan Feng

IEEE Transactions on Computers · 2026-07 · 75 (7) · 2632-2645

DOI: 10.1109/tc.2026.3689925 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Computers, 2026-07. Verfasst von Yibo Liu und 7 weiteren Autor:innen. Die Arbeit nennt 45 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

B ${}^{+}$ + -Trees are widely used in storage systems and diverse applications. However, their performance is hindered by frequent memory accesses required for key comparisons and structural maintenance. The limited parallelism of CPUs, along with their sensitivity to data order and volume, further restricts the efficiency of B ${}^{+}$ + -Trees. Processing-in-memory (PIM) offers a promising alternative with its in-situ parallel computing capability. In this paper, we propose pTree, a novel set of PIM techniques and architecture specifically designed to accelerate B ${}^{+}$ + -Tree operations. pTree introduces in-situ parallel comparison mechanisms that significantly reduce costly memory accesses and inefficient CPU-side comparisons during tree traversal. This parallelism eliminates the need to maintain intra-node key order and, together with our in-situ parallel node bisecting techniques, greatly minimizes tree structure maintenance overhead during insertions and deletions. Additionally, pTree decouples both comparison and modification efficiency from node size, enabling the use of larger nodes to reduce tree height and traversal complexity. Evaluation shows that pTree reduces the average latency to 35%, 26%, 52%, and 32% compared to state-of-the-art B ${}^{+}$ + -Trees for Insert , Search , Update , and Delete operations.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Liu, Y., Wu, B., Song, S., Wei, X., Cheng, H., Zhou, H., Tong, W., & Feng, D. (2026). pTree: Building Efficient B+-Tree on Non-Volatile Memory With Processing-in-Memory. IEEE Transactions on Computers, 75(7), 2632-2645. https://doi.org/10.1109/tc.2026.3689925

Vancouver

Liu Y, Wu B, Song S, Wei X, Cheng H, Zhou H, et al. pTree: Building Efficient B+-Tree on Non-Volatile Memory With Processing-in-Memory. IEEE Transactions on Computers. 2026;75(7):2632-2645. doi:10.1109/tc.2026.3689925

BibTeX
@article{Liu2026,
  author = {Liu, Yibo and Wu, Bing and Song, Shiyi and Wei, Xueliang and Cheng, Huan and Zhou, Heng and Tong, Wei and Feng, Dan},
  title = {pTree: Building Efficient B+-Tree on Non-Volatile Memory With Processing-in-Memory},
  journal = {IEEE Transactions on Computers},
  year = {2026},
  volume = {75},
  number = {7},
  pages = {2632--2645},
  doi = {10.1109/tc.2026.3689925}
}
Kostenlos starten →