Memory Management and B-Trees

Memory Management and B-Trees

1. Memory Management

   • 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.
     • Allocating Space in the Memory Heap
       • Dynamic Memory Allocation
       • The Memory Heap
     • Garbage Collection
       • The Mark-Sweep Algorithm
       • Performing DFS In-Place

2. Memory Hierarchies and Caching

   • Memory Systems
   • Caching Strategies

3. External Searching and B-Trees

   • (a,b) Trees
     • Multiway search tree such that each node has between a and b children and stores between a−1 and b−1 entries.
   • B-Trees
     • A version of the (a,b) tree data structure, which is the best-known method for maintaining a map in external memory.

4. External-Memory Sorting

   • Multiway Merge-Sort
     • The main idea behind this variation is to merge many recursively sorted lists at a time, thereby reducing the number of levels of recursion.

Images and files in the map