Data Structures and Algorithms in Python

Chapter 15

Memory Management and B-Trees

Contents

15.1 Memory Management

15.1.1 Memory Allocation

15.1.2 Garbage Collection

15.1.3 Additional Memory Used by the Python Interpreter

15.2 Memory Hierarchies and Caching

15.2.1 Memory Systems

15.2.2 Caching Strategies

15.3 External Searching and B-Trees

15.3.1 (a,b) Trees

15.3.2 B-Trees

15.4 External-Memory Sorting

15.4.1 Multiway Merging

15.5 Exercises

Our study of data structures thus far has focused primarily upon the efficiency of computations, as measured by the number of primitive operations that are executed on a central processing unit (CPU). In practice, the performance of a computer system is also greatly impacted by the management of the computer's memory systems. In our analysis of data structures, we have provided asymptotic bounds for the overall amount of memory used by a data structure. In this chapter, we consider more subtle issues involving the use of a computer's memory system.

We first discuss ways in which memory is allocated and deallocated during the execution of a computer program, and the impact that this has on the program's performance. Second, we discuss the complexity of multilevel memory hierarchies in today's computer systems. Although we often abstract a computer's memory as consisting of a single pool of interchangeable locations, in practice, the data used by an executing program is stored and transferred ...