A supermarket chain wants you to implement an in-memory database that can be used to access facts about the products they sell. Although a snapshot of this database will be periodically copied to disk, its contents fit in memory, and your component of the application will operate only on data stored in memory.

Here are the requirements specified by the managers of the supermarket chain:

• They want to be able to retrieve product records by specifying the name of the product.
• They want to be able to specify the first n characters of a product name and to retrieve all records that begin with those characters.
• They want the time required to retrieve a record to be as efficient as possible - on the order of 20 operations per retrieval, given a database of approximately one million records.
• They want to be able to increase the size of the database - adding large sets of new records - without taking the system offline.

Given this list of requirements, which data structure would be the better choice for this application, a balanced search tree (e.g., a 2-3 tree) or a hash table - or would these two data structures work equally well?

Explain your decision, specifying as many reasons as possible for the choice that you make.