CSE 326, Spring 1997: Homework 8

Due 5/28/97

  1. (20 points) The purpose of this problem is to analyze and compare B-trees and extendible hashing as two alternatives for maintaining a large data base. Imagine that you have been asked to to implement a new IRS database. There are 50,000,000 records, each of which take an average of 2,000 bytes. The records are keyed with a Social Security Number which is 4 bytes. The computer that you will be using has 2,048 byte pages and pages are addressed with 4 byte integers. Assume that the computer has 16 MB of memory that is usable for storing all or part of a search structure.
  2. (10 points) Consider an array with the following data in it: 14,2,3,20,15,10,13,6,9.