Advanced Programming in the UNIX® Environment

ptg10805159

Section 20.4 Implementation Overview 747

Withdb_store,only one recordfor each key is allowed. Some database systems

allow a key to have multiple records and then provide a way to access all the records

associated with a given key.Additionally, we have only a single index file, meaning

that each data recordcan have only a single key (we don’t support secondary keys).

Some database systems allow each record to have multiple keys and often use one index

file per key.Each time a new recordisinserted or deleted, all index files must be

updated accordingly.(An example of a file with multiple indexes is an employee file.

We could have one index whose key is the employee ID and another whose key is the

employee’s Social Security number.Having an index whose key is the employee name

could be a problem, as names arenot always unique.)

Figure20.2 shows a general picture of the database implementation.

index file: freeptr chainptr chainptr ... chainptr \n

chain

ptr

idx

len key sep

dat

off sep

dat

len \n

data file: data \n

hash table

index records

one index record

idx len

one data record

dat len

offset of first index

record on freelist

offset of first index

record on this hash chain

offset of next index

record on this hash chain

Figure 20.2 Arrangement of index file and data file

The index file consists of three portions: the free-list pointer,the hash table, and the

index records. In Figure20.2, all the fields calledptraresimply file offsets stored as an

ASCII number.