Data Structures and Algorithms in Java, 6th Edition

Chapter 15

Memory Management and B-Trees

Contents

15.1 Memory Management

15.1.1 Stacks in the Java Virtual Machine

15.1.2 Allocating Space in the Memory Heap

15.1.3 Garbage Collection

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

15.1 Memory Management

Computer memory is organized into a sequence of words, each of which typically 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 memory address. Thus, the memory in a computer can be viewed as basically one giant array of memory words, as portrayed in Figure 15.1.

Figure 15.1: Memory addresses.

In order to run programs and store information, the computer's memory must be managed so as to determine what data is stored in what memory cells. In this section, we discuss the basics of memory management, most notably describing the way in which memory is allocated for various purposes in a Java program, and the way in which portions of memory are deallocated and reclaimed, when no longer ...