O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 14. Memory Management and B-Trees

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required