Advanced Programming in the UNIX® Environment

ptg10805159

Section 20.4 Implementation Overview 749

when we wrote the record to the database. The data offset( 0 )and data length( 6 )refer

to the data file.We can see that the data recorddoes start at offset 0 in the data file and

has a length of 6 bytes.

#include "apue.h"

#include "apue_db.h"

#include <fcntl.h>

int

main(void)

{

DBHANDLE db;

if ((db = db_open("db4", O_RDWR | O_CREAT | O_TRUNC,

FILE_MODE)) == NULL)

err_sys("db_open error");

if (db_store(db, "Alpha", "data1", DB_INSERT) != 0)

err_quit("db_store error for alpha");

if (db_store(db, "beta", "Data for beta", DB_INSERT) != 0)

err_quit("db_store error for beta");

if (db_store(db, "gamma", "record3", DB_INSERT) != 0)

err_quit("db_store error for gamma");

db_close(db);

exit(0);

}

Figure 20.3Create a database and write three records to it

(As with the index file, we automatically append a newline to each data record, so we

can use the normal UNIX System tools with the file. This newline at the end is not

returned to the caller bydb_fetch.)

If we follow the three hash chains in this example, we see that the first recordonthe

first hash chain is at offset 53 (gamma). The next record on this chain is at offset 17

(alpha), and this is the last record on the chain. The first record on the second hash

chain is at offset 35 (beta), and it’s the last record on the chain. The thirdhash chain is

empty.

Note that the order of the keys in the index file and the order of their corresponding

records in the data file is the same as the order of the calls todb_storein Figure20.3.

Since theO_TRUNCflag was specified fordb_open,the index file and the data file were

both truncated and the database initialized from scratch. In this case,db_storejust

appends the new index records and data records to the end of the corresponding file.

We’ll see later thatdb_storecan also reuse portions of these two files that correspond

to deleted records.

The choice of a fixed-size hash table for the index is a compromise. It allows fast

access as long as each hash chain isn’t too long.We want to be able to search for any

key quickly,but we don’t want to complicate the data structures by using either a B-tree

or dynamic hashing. Dynamic hashing has the advantage that any data recordcan be