boltdb/bolt — pull request #127 by benbjohnson (2014-04-09 14:45:49+00:00)
Title: Add nested buckets.

## Overview

> *WIP: This pull request passes all existing tests but more tests need to be added.*

This pull request adds the ability to nest buckets inside of other buckets. It also replaces the buckets page with a root bucket. This pull request looks bigger than it is. It's mostly moving a lot of `Tx` functionality over to the `Bucket`.

## API Changes

Previously, the ability to create, retrieve, and delete buckets was entirely in `Tx` and `buckets`. This made sense because buckets were a top-level construct. Now that buckets can exist inside other buckets, all this functionality has moved to the `Bucket` type.

Buckets and simple byte slice values all exist in the same keyspace. You can mix buckets and byte slice values together so creating a subbucket called "widgets" and putting a key called "widgets" will cause the bucket to be overwritten.

### New Bucket functions:

```go
func (b *Bucket) Bucket(name []byte) *Bucket
func (b *Bucket) CreateBucket(key []byte) error
func (b *Bucket) CreateBucketIfNotExists(key []byte) error
```

### Changes in Bucket functions:

* If you `Get()` a key that is a subbucket then nil is returned.

* If you `Put()` to a key that is a subbucket then the subbucket will be deleted and overwritten with a byte slice.

* `Delete()` works for both keys and subbuckets.

### Tx functions

All the previous Tx bucket functions still exist and simply wrap the root bucket's same functions:

```go
func (tx *Tx) Bucket(name []byte) *Bucket
func (tx *Tx) CreateBucket(name []byte) error
func (tx *Tx) CreateBucketIfNotExists(name []byte) error
func (tx *Tx) DeleteBucket(name []byte) error
```

However, since buckets are in the regular keyspace, their names are byte slices instead of strings.

## File Format Changes

Allowing buckets to be nested made the `buckets` page redundant. Now, instead of a specialized page type,
there is a root bucket that the `Tx` uses to find and create top-level buckets. This root bucket is only accessible to the `Tx` so it only stores buckets (e.g. no simple byte slice values).

Because of this change, older Bolt databases are not compatible after this pull request is merged. I'll be merging in an import/export tool through a separate PR before this pull request is merged. That will allow databases to be exported to a generalized JSON format and imported into a new version of Bolt.

The data format `version` has been bumped to `2` with this PR. Opening previous data format versions of the database will return `ErrVersionMismatch` error.

## Other Notes

This pull request lacks a few optimizations that will be coming in future PRs:

1. Inline buckets (#124) - Currently buckets require their own root page. Inlining buckets would allow small buckets (`< pageSize`) to be written with their data into the same value that their `bucket` header exists.

2. Allocations (#125) - Currently subbuckets require allocation of a `Bucket` for access. This is mostly to track nodes for each bucket but that shouldn't be required for read-only transactions. Tweaking this should make iteration faster for nested buckets.

3. Cursor Reuse (#126) - If someone is iterating over two levels of buckets then they should be able to only allocate two cursors and reuse them for each level. Currently Bolt requires a new cursor after every change in a higher level bucket.

---

Fixes #56.

/cc @tv42 @snormore @mkobetic