db

README

Berkeley DB 1.85 implementation in pure Go

Btree, hash and recno access methods, file format compatible with dbopen(3) of 4.4BSD (and macOS/FreeBSD libc). No dependencies beyond the standard library.

go get github.com/dim13/db

Package	Access method
btree	sorted keys, optional duplicates
hash	linear hashing
recno	records of a flat text file by number
ndbm	ndbm(3) interface on hash
hsearch	hsearch(3) in-memory table on hash

Each access method has a New(file, info) returning a *DB that implements db.DB. A nil file gives an in-memory database, an empty file a new one, and a nil Info the defaults.

f, err := os.OpenFile("test.db", os.O_RDWR|os.O_CREATE, 0644)
if err != nil {
	log.Fatal(err)
}
d, err := btree.New(f, nil)
if err != nil {
	log.Fatal(err)
}
defer d.Close()

d.Put([]byte("key"), []byte("value"), db.RNone)
v, err := d.Get([]byte("key"), db.RNone)
if err != nil {
	log.Fatal(err) // errors.Is(err, db.ErrNotFound) if missing
}
fmt.Printf("%s\n", v)

for k, v, err := d.Seq(nil, db.RFirst); err == nil; k, v, err = d.Seq(nil, db.RNext) {
	fmt.Printf("%s=%s\n", k, v)
}

Routine flags (db.RCursor, db.RFirst, ...) and errors are those of the C interface, see package db. A database is safe for concurrent use: Get calls run in parallel, other methods one at a time, and Seq has a single cursor shared by all callers.

ndbm.Open(name, flag, perm) opens name.db with os.OpenFile flags and returns a *DBM that implements db.DBM:

d, err := ndbm.Open("test", os.O_RDWR|os.O_CREATE, 0644)
if err != nil {
	log.Fatal(err)
}
defer d.Close()

d.Store([]byte("key"), []byte("value"), db.DBMReplace)
for k, err := d.FirstKey(); err == nil; k, err = d.NextKey() {
	fmt.Printf("%s\n", k)
}

File formats are described in doc/btree.txt, doc/hash.txt and doc/recno.txt.

Differences to the C implementation

• Pages are cached in an LRU cache of Info.CacheSize bytes (default 1 MiB), evicted between operations only. In-memory databases are not spilled to a temporary file, their cache is unbounded.
• Read-only mode is set by Info.ReadOnly, not detected from the file.
• Put returns the key it stored under; recno returns the new record number, also for R_IAFTER, as later C versions do.
• A recno Info with zero Delimiter delimits records by newline, C uses NUL when parameters are passed.
• Fixed 1.85 bugs: big keys searched by overflow reference on put, prefix taken against a big key, overfull pages and empty right pages on split, page deletes after search stepped to a sibling, lost btree free list on reopen, hash big pairs filling a page exactly, squeezing pairs onto a big pair tail, overflow page 2047 never reused.
• Non-native byte order btrees written by C with overflow data but inline key are not readable (C's bt_conv.c swaps the wrong bytes there).
• ndbm returns errors instead of dbm_error/dbm_clearerr, and Close reports write errors. dbm_forder and dbm_pagfno are not provided.
• hsearch is a value type (hsearch.Table) instead of one global table.

Documentation

Overview

Package db defines the interfaces, routine flags and errors shared by the Berkeley DB 1.85 access methods in packages btree, hash and recno, and the ndbm interface in package ndbm.

Index

• Variables
• type DB
• type DBM
• type Flag
• type Mode

Variables

var (
	ErrNotFound = errors.New("not found")      // key not found or no more keys
	ErrKeyExist = errors.New("key exists")     // put with RNoOverwrite
	ErrInvalid  = errors.New("invalid")        // bad argument
	ErrReadOnly = errors.New("read only")      // change to read-only database
	ErrFormat   = errors.New("invalid format") // not a database file
	ErrOverflow = errors.New("out of overflow pages, increase page size")
	ErrNoPage   = fmt.Errorf("%w: no such page", ErrFormat) // link past end of file
	ErrPageType = fmt.Errorf("%w: page type", ErrFormat)    // unexpected page type
)

Errors returned by the access methods, to be checked with errors.Is.

Types

type DB

type DB interface {
	// Close syncs the database and closes its files.
	Close() (err error)
	// Del deletes key, or with RCursor the entry at the cursor.
	Del(key []byte, flag Flag) (err error)
	// Fd returns the file descriptor, or ^uintptr(0) for an in-memory
	// database.
	Fd() (fd uintptr)
	// Get returns the data stored under key, or ErrNotFound.
	Get(key []byte, flag Flag) (data []byte, err error)
	// Put stores data under key and returns the key it is stored under,
	// which differs from key only for recno insertions.
	Put(key []byte, data []byte, flag Flag) (rkey []byte, err error)
	// Sync writes all changes to disk.
	Sync(flag Flag) (err error)
	// Seq returns the next key/data pair of a sequential scan, or
	// ErrNotFound at its end.  RFirst, RLast and RCursor start a scan,
	// RNext and RPrev continue it.
	Seq(key []byte, flag Flag) (rkey []byte, data []byte, err error)
}

DB is an open database, the counterpart of the C DB handle. Implementations are safe for concurrent use: Get calls run in parallel, other methods one at a time; Seq has a single cursor shared by all callers.

type DBM

type DBM interface {
	// Close writes changes and closes the file.
	Close() (err error)
	// Fetch returns the content stored under key, or ErrNotFound.
	Fetch(key []byte) (content []byte, err error)
	// Store stores content under key.  With DBMInsert an existing key is
	// kept and ErrKeyExist returned.
	Store(key, content []byte, mode Mode) (err error)
	// Delete deletes key, or returns ErrNotFound.
	Delete(key []byte) (err error)
	// FirstKey returns the first key, or ErrNotFound if the database is
	// empty.
	FirstKey() (key []byte, err error)
	// NextKey returns the key after the one returned last, or ErrNotFound
	// at the end.
	NextKey() (key []byte, err error)
	// DirFd returns the file descriptor of the database file.
	DirFd() (fd uintptr)
}

DBM is an open ndbm database, the counterpart of the C DBM handle. Implementations are safe for concurrent use; FirstKey and NextKey share a single cursor.

type Flag

type Flag uint

Flag selects the operation of a DB method, values as in C.

const (
	RNone   Flag = iota // no flag
	RCursor             // del, put, seq

	RFirst       // seq
	RIAfter      // put (recno)
	RIBefore     // put (recno)
	RLast        // seq (btree, recno)
	RNext        // seq
	RNoOverwrite // put
	RPrev        // seq (btree, recno)
	RSetCursor   // put (recno)
	RRecnoSync   // sync (recno)
)

Routine flags

type Mode

type Mode int

Mode selects what DBM.Store does with an existing key.

const (
	DBMInsert  Mode = iota // keep existing data, return ErrKeyExist
	DBMReplace             // overwrite existing data
)

Store modes