Performance analysis of BSTs in system software
- 1 June 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 32 (1), 410-411
- https://doi.org/10.1145/1012888.1005742
Abstract
Binary search tree (BST) based data structures, such as AVL trees, red-black trees, and splay trees, are of- ten used in system software, such as operating system kernels. Choosing the right kind of tree can impact performance significantly, but the literature oers few empirical studies for guidance. We compare 20 BST variants using three experiments in real-world scenar- ios with real and artificial workloads. The results in- dicate that when input is expected to be randomly or- dered with occasional runs of sorted order, red-black trees are preferred; when insertions often occur in sorted order, AVL trees excel for later random access, whereas splay trees perform best for later sequential or clustered access. For node representations, use of parent pointers is shown to be the fastest choice, with threaded nodes a close second choice that saves mem- ory; nodes without parent pointers or threads suer when traversal and modification are combined; main- taining a in-order doubly linked list is advantageous when traversal is very common; and right-threaded nodes perform poorly.Keywords
This publication has 6 references indexed in Scilit:
- Self-adjusting binary search treesJournal of the ACM, 1985
- Internet Protocol1981
- An empirical evaluation of algorithms for dynamically maintaining binary search treesPublished by Association for Computing Machinery (ACM) ,1980
- A dichromatic framework for balanced treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- A comparison of tree-balancing algorithmsCommunications of the ACM, 1977
- Performance of height-balanced treesCommunications of the ACM, 1976