B堆
外觀
B堆(英語:B-heap)是一個用來保證子樹在一個內存頁的二叉堆。這樣可以在使用虛擬內存時減少訪問很大堆時內存頁的訪問。傳統的實現中,元素位置的映射(幾乎)每一級都放在不同的內存頁中。
也有其他非常高效實用虛擬內存和緩存的堆的變種,例如緩存忽略算法、k堆、[1]和van Emde Boas樹。[2]
參見
[編輯]參考文獻
[編輯]- ^ Naor, Dalit; Martel, Charles U.; Matloff, Norman S. Performance of Priority Queue Structures in a Virtual Memory Environment. Comput. J. 1991, 34 (5): 428–437. doi:10.1093/comjnl/34.5.428.
- ^ van Emde Boas, P.; Kaas, R.; Zijlstra, E. Design and implementation of an efficient priority queue. Mathematical Systems Theory. 1976, 10: 99–127. doi:10.1007/BF01683268.[失效連結]
外部連結
[編輯]- 實現: https://archive.today/20130416023425/http://www.varnish-cache.org/trac/browser/lib/libvarnish/binary_heap.c and http://phk.freebsd.dk/B-Heap/binheap.c(頁面存檔備份,存於網際網路檔案館)
- Generic heap implementation with B-heap support(頁面存檔備份,存於網際網路檔案館).
- 更多參見:van Emde Boas layouts see Benjamin Sach Descent into Cache-Oblivion(頁面存檔備份,存於網際網路檔案館) or Cache-oblivious data structures(頁面存檔備份,存於網際網路檔案館).
![]() | 這是一篇電腦科學小作品。您可以透過編輯或修訂擴充其內容。 |