Data Structures and Algorithms in C++, Second Edition

Chapter 14. Memory Management and B-Trees

Contents

14.1 Memory Management	666
14.1.1 Memory Allocation in C++	669
14.1.2 Garbage Collection	671
14.2 External Memory and Caching	673
14.2.1 The Memory Hierarchy	673
14.2.2 Caching Strategies	674
14.3 External Searching and B-Trees	679
14.3.1 (a,b) Trees	680
14.3.2 B-Trees	682
14.4 External-Memory Sorting	683
14.4.1 Multi-Way Merging	684
14.5 Exercises	685

Memory Management

In order to implement any data structure on an actual computer, we need to use computer memory. Computer memory is simply a sequence of memory words, each of which usually consists of 4, 8, or 16 bytes (depending on the computer). These memory words are numbered from 0 to N − 1, where N is the number of memory words available to the computer. The number associated with each memory word is known as its address. Thus, the memory in a computer can be viewed as basically one giant array of memory words. Using this memory to construct data structures (and run programs) requires that we manage the computer's memory to provide the space needed for data—including variables, nodes, pointers, arrays, and character strings—and the programs the computer runs. We discuss the basics of memory management in this section.

The C++ Run-Time Stack

A C++ program is compiled into a binary executable file, which is then executed within the context of the C++ run-time environment. The run-time environment provides ...