Technique of clustering and compaction of binary trees

摘要

A technique for improving the performance of binary tree operations involves defining an implicit binary tree structure in a memory array, and clustering of the nodes of the tree in memory in a cache-aware manner. The technique reduces memory latency by improved spatial locality of the binary tree data, and further improves cache performance through reduced size of the data objects resulting from elimination of pointers to other nodes of the tree.