Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1092344402.pdf (1.38 MB)

ETD Abstract Container

Abstract Header

B+ TREE CACHE MEMORY PERFORMANCE

GIESKE, EDMUND J
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1092344402

Abstract Details

2004, MS, University of Cincinnati, Engineering : Computer Engineering.
Computer systems use indices to quickly access particular data or files. Various data structures are used to implement different types of indices. One data structure, the B+Tree, is commonly used to index large databases and file systems. B+Trees were developed to efficiently bridge the wide speed difference between a computer’s main memory and its online storage. The large main memory capacity of today’s computers has reduced the importance of bridging that speed difference. Now, the speed difference between a computer’s central processor unit (CPU) and main memory is the main determinant of database or file system index performance. This has led to a reexamination of the B+Tree and a revision of its internal structure. The performances of two styles of B+Tree index structures are compared. This thesis begins with an analytic B+Tree performance model that motivates restructuring B+Tree nodes into two arrays, one of keys and another of child pointers, instead of the traditional array of tuples. We call trees composed of the restructured nodes “two-arrays based B+Trees” or TAB+Trees. Hardware execution of both types of trees with identical contents shows that average execution time improves by at least 8.3%. This overall speed improvement is mostly due to a 9% reduction in cache misses. TAB+Trees are also found to be more scalable in that they incur fewer cache misses when constructed with larger nodes. Trees composed of larger nodes in turn incur fewer data translation look aside buffer (DTLB) search cycles. Since DTLB misses can be almost eliminated with custom memory allocation, second level cache misses are found to be the dominant factor in execution time for large trees. The performances of various sizes of TAB+Trees across a wide variety of secondary cache configurations are simulated, showing predictable behavior. This culminates in a simplified model of B+Tree execution time. We conclude with suggestions for further refinements to TAB+Trees and other data structures similar to B+Trees.
Dr. Harold Carter (Advisor)
54 p.
B+Tree; Cache Memory Conscious; Data Structure; File System Index; Database Table

Recommended Citations

Citations

  • GIESKE, E. J. (2004). B+ TREE CACHE MEMORY PERFORMANCE [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1092344402

    APA Style (7th edition)

  • GIESKE, EDMUND. B+ TREE CACHE MEMORY PERFORMANCE. 2004. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1092344402.

    MLA Style (8th edition)

  • GIESKE, EDMUND. "B+ TREE CACHE MEMORY PERFORMANCE." Master's thesis, University of Cincinnati, 2004. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1092344402

    Chicago Manual of Style (17th edition)

ucin1092344402
834
© 2004, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.