.GDBM File Format

Introduction

GNU GDBM is a library that keeps keys and data of any length in a file, as an extendible hash table. This is that file. It is a format of its own, older than SQLite and used by many programs. It is also what SQLite 1.0, released in August 2000, wrote: the one version of SQLite whose database is not a file but a folder, in which each table and each index is a GDBM file of its own, named with .tbl added. SQLite 2.0 (2001) replaced that with a b-tree of SQLite’s own in a single file and could not read the old folders; SQLite 1.0 is therefore not a version of the SQLite database format.

So there are two layers. The lower one is GDBM: a hash table kept in a file, with keys and data of any length. The upper one is SQLite 1.0’s own: how a table’s rows, an index’s entries and the schema are written as GDBM keys and data. This page describes both, as they are in the source of GDBM and of SQLite 1.0.4 (28 August 2000), the earliest 1.0 source on the SQLite repository’s history that this page was checked against.

Drop the database’s folder on this site and the explorer lists the schema, every table’s rows and every index’s entries, and shows every GDBM file beside them. Drop one .tbl file, or any GDBM file, and the explorer shows the GDBM structures in file order, byte for byte, and SQLite 1.0’s layout over the records.

The database folder

A database is a folder. SQLite 1.0 checks that the path is a folder and that sqlite_master.tbl can be reached in it. Every table and index is then one GDBM file named after it with .tbl added. The name is made lower case, and each byte that is not a letter, a digit, -, _ or . becomes +, so a table called My Table is my+table.tbl. (SQLite’s code works on bytes, so a character that takes two bytes in UTF-8 gives two +.) The two names My Table and my table would therefore share a file.

Other files that can be in the folder:

• sqlite_master.tbl – the schema table, below.
• _temp_table_ and a random suffix – a temporary table, a GDBM file that SQLite deletes when its last cursor closes.
• _temp_file_ and a random suffix – a temporary plain file, not GDBM, used for sorting; deleted when closed.

SQLite opens a table’s file with GDBM_WRCREAT | GDBM_FAST to write and GDBM_READER to read, with the default block size and mode 0640. Nothing else in SQLite 1.0 locks a database; it relies on GDBM and on the file permissions. A table that has no file reads as empty.

SQLite 1.0’s layout over GDBM

Every value in SQLite 1.0 is text, so a number is stored as its digits. Whole numbers in the layout below (keys, offsets, counts) are 4-byte integers in the byte order of the machine that wrote the file, which is also GDBM’s byte order, so the file’s magic number tells both.

A table file

Each row is one GDBM pair.

The number of columns is not stored with a row; it is the number of columns in the table’s CREATE TABLE statement, or the length of the offset table: the first non-zero offset divided by 4.

An index file

There is one pair for each distinct indexed value.

sqlite_master

sqlite_master.tbl is an ordinary table file of four columns. Its definition in SQLite’s source is CREATE TABLE sqlite_master (type text, name text, tbl_name text, sql text).

SQLite writes the meta row when it creates the first table. When a database is opened SQLite reads the rows, and for a meta row it reads the number after file format and ignores any other meta text. A database with no meta row is file format 1, and SQLite 1.0.4 refuses to open a file format 1 database that has tables, with the message “obsolete file format”.

The GDBM file

A GDBM file is an extendible hash table. Its pieces are a header, a directory of addresses, buckets that hold the hash table’s elements, the records, and lists of free space. Everything below is from GDBM’s gdbmdefs.h, gdbmconst.h, hash.c, bucket.c, falloc.c and gdbmopen.c. The C structures are written to the file as they are in memory, so a file has the byte order of the machine that wrote it, an int of 4 bytes, and a file address (off_t) of 4 or 8 bytes. An 8-byte address is aligned to 8 bytes inside a structure, which adds padding.

The header

Block 0 is the header, and it takes a whole block (the block size, usually 512 to 4,096 bytes). It starts with gdbm_file_header.

The header is 32 bytes with 4-byte addresses and 40 with 8-byte ones.

The same numbers byte-swapped (0xCE9A5713, 0xCD9A5713, 0xCF9A5713, 0xD09A5713, 0xD19A5713) mean the file was written on a machine of the other byte order; that tells which order every number in the file is in.

The numsync magic numbers (GDBM’s synchronisation counter, which a file of the year 2000 will not have) put a 32-byte extension header, gdbm_ext_header, directly after the file header: a version (an int, 0), the number of synchronisations (an unsigned int) and six spare ints.

Free space: avail tables

GDBM keeps a list of free blocks, each an avail_elem: a size (av_size, 4 bytes) and a file address (av_adr, with 4 padding bytes before it when addresses are 8 bytes). It is 8 bytes with 4-byte addresses and 16 with 8-byte ones. The lists are kept in order of size, and there are three kinds.

• The header’s table. An avail_block follows the header (and the extension header): size (how many entries the table has room for), count (how many are in use), next_block (the address of the first avail block in the file, or 0), then the entries. These fields take 12 bytes with 4-byte addresses and 16 with 8-byte ones. size is what fits in the rest of the header block: the block size, minus what comes before the table and the 12 or 16 bytes, divided by the entry size.
• Each bucket’s table, six entries (BUCKET_AVAIL), of which av_count are in use. It keeps small blocks near the bucket so that freeing and allocating them changes only the bucket.
• Avail blocks in the file, chained from the header’s next_block. When the header’s table is full, half of its entries (the odd-numbered ones) move to a new block, which is allocated from the table itself, and the header’s next_block now points to it, with the block’s next_block taking the old value. When the table is at most half full and there is a block, it is read back in. A block is the avail block’s fixed part (the 12 or 16 bytes and room for one entry) plus half the header table’s entries, so that is its size in the file.

Blocks of 4 bytes or fewer (IGNORE_SIZE) are not listed. Neighbouring free blocks are merged when one is freed. To allocate, GDBM takes the first block that fits from the bucket’s table, then the header’s, and otherwise extends the file at next_block by whole blocks and frees the unused end. A chunk of at least a block, and any chunk when the file is in central-free mode, goes to the header’s table; smaller ones go to the bucket’s.

The directory

At dir are 2^dir_bits file addresses of buckets. A key’s hash (31 bits) is used from the top: its top dir_bits bits are the number of the entry. When a bucket fills it splits in two; if it already used all dir_bits bits the directory doubles first, each entry copied into two neighbours. So a bucket that has used only bucket_bits bits is pointed to by 2^{dir_bits − bucket_bits} consecutive entries, the first at a multiple of that number. A new file has one bucket and every entry points to it.

Buckets and their elements

A hash_bucket is bucket_size bytes.

A bucket_element is 20 bytes with 4-byte addresses and 24 with 8-byte ones.

A key goes to the slot given by its hash modulo bucket_elems. If that slot is taken the next is tried, and so on, wrapping round (linear probing). When a bucket splits, each element goes to one of the two new buckets by the next bit of its hash.

Records

At an element’s data_pointer the key’s bytes are followed at once by the data’s bytes: key_size + data_size bytes, with no length, no terminator and no padding. When a record is replaced or deleted its space goes to an avail list. Free space and the slack at the end of a record that was given a larger block are both “free” to GDBM, but only blocks of more than 4 bytes are listed, so some bytes of a working file belong to nothing.

The hash function

From hash.c, in 32-bit unsigned arithmetic:

value = 0x238F13AF * key_size;
for each byte i of the key:
    value = (value + (byte[i] << (i * 5 % 24))) & 0x7FFFFFFF;
value = (1103515243 * value + 12345) & 0x7FFFFFFF;

The result is the 31-bit hash. Current GDBM takes the bytes as unsigned. An older GDBM that took them as C char, which is signed on most machines, would give a different hash for a key byte of 0x80 or more, so the explorer accepts either as matching the stored hash (the older source was not read).

The first layout

A new file has the header in block 0, the directory in block 1 (its size is the block size), one bucket in block 2, one free block of a block’s size at block 3 listed in the header’s table, and next_block at block 4, where the file is extended to.

Byte order

Neither SQLite 1.0 nor GDBM converts anything: every number is in the byte order of the machine that wrote the file, so a database cannot be moved between machines of different byte orders. The GDBM magic number shows the order, and SQLite’s own numbers (the row keys, offsets and counts) share it.

Telling it apart

A folder with a sqlite_master.tbl whose files each start with a GDBM magic number is an SQLite 1.0 database. A single GDBM file is not by itself SQLite: other programs use GDBM, and a file of an SQLite 1.0 database does not say whether it is a table, an index or the schema. The explorer decides from the file’s name (sqlite_master.tbl) and by testing the records against the table layout and the index layout, and the Overview says how it decided; in a dropped folder, sqlite_master states it.

Not described

Unknown

• Reference and viewer: file format 1, the databases that have no meta row. The SQLite 1.0.4 source reads a database as file format 1 when there is no meta row and refuses it as “obsolete” if it has tables; nothing in the source or in SQLite’s documentation says what a file format 1 database looked like, so it is read as the layout above and not checked against another.
• Reference and viewer: SQLite 1.0.0 to 1.0.3. The layout above is from the 1.0.4 source, and the earlier releases’ source was not read, so a difference in them is not known.
• Viewer: the explorer’s reading of the GDBM structures follows GDBM’s source, but no real GDBM or SQLite 1.0 file was available to check it with: its tests use files built by hand to the same structures.

Related formats

• SQLite database – SQLite 1.0 stored its tables in GDBM files; SQLite 2 and 3 each have a single-file format of their own, a different format from this one

Links