boltdb/bolt — pull request #21 by benbjohnson (2014-02-11 16:50:59+00:00)
Title: Cursor iteration.

## Overview

This pull request includes the ability to iterate over an entire bucket by using a cursor. Currently cursors are unidirectional and can only move forward.

## Usage

Bolt is organized as a B+tree which means that all the data is held in the leaf nodes so it's fast and easy iterate over them. You can create a cursor from any `Transaction`:

```go
// Open a cursor on your "widgets" bucket.
txn, err := db.Transaction()
defer txn.Close()
c := txn.Cursor("widgets")
```

Once you have your cursor you can point to the first key/value pair by calling `Cursor.First()`:

```go
key, value := c.First()
```

And then you can get the next key/value pair by calling `Cursor.Next()`:

```go
key, value = c.Next()
```

Both functions will return `nil` when no more key/value pairs are found. The idiomatic way to iterate over all key/value pairs in a bucket is like this:

```
for k, v := c.First(); k != nil; k, v = c.Next() {
// Do stuff.
}
```

Cursors do not need to be explicitly closed. They'll be cleaned up automatically when a `Transaction` is closed.

## How It Works

Cursors are really simple. They are composed of a pointer to a bucket's root page and a stack of page/index items. Calling `First()` will start from the cursor's root page and will recursively add the left-most page to the top of the stack.

For example, say we have a B+tree like this:

```
===0===
| d|g |
|1|2|3|
=======
| | |
------ | -------
| | |
===1=== ===2=== ===3===
|a|b|c| |d|e|f| |g|h|i|
|-|-|-| |-|-|-| |-|-|-|
|*|*|*| |*|*|*| |*|*|*|
```

Here we have a root branch node of `0` and three leaf nodes (`1`, `2`, `3`). Calling `First()` will setup our cursor's stack to be:

```
=============
|pgid | idx |
| 0 | 0 |
| 1 | 0 |
=============
(key=a)
```

As we call `Next()`, we increment the index on the top of our stack:

```
============= ============= =============
|pgid | idx | |pgid | idx | |pgid | idx |
| 0 | 0 | -> Next() -> | 0 | 0 | -> Next() -> | 0 | 0 |
| 1 | 0 | | 1 | 1 | | 1 | 2 |
============= ============= =============
(key=a) (key=b) (key=c)
```

Now that we're at the end of our first leaf page, calling `First()` again will cause the cursor to move up the stack and move the index on the parent branch page and then move down to the second leaf node:

```
============= ============= ============= =============
|pgid | idx | |pgid | idx | |pgid | idx | |pgid | idx |
| 0 | 0 | -> Next() -> | 0 | 0 | -> | 0 | 1 | -> | 0 | 1 |
| 1 | 2 | ============= ============= | 2 | 0 |
============= =============
(key=c) (key=d)
```

Now that we're on our second leaf node we can iterate through each of its values. We'll move back up the stack and find our last leaf when we get to the end of the second leaf.

Once we get to the end of the last leaf, we clear the stack and return `nil` to let the user know that there are no more values.

## Caveats

There are a few important things to know when working with cursors:

1. It is important to not use a cursor after a `Transaction` has been closed. A transaction keeps pages from being reclaimed until the transaction is closed so using a cursor on a closed transaction could point to rewritten pages which will probably crash your program (or at least return bad data).

2. A `RWTransaction` can use cursors (since it's composed of a `Transaction`) but these writer transactions hold changed nodes in-memory so inserted or deleted values will not be reflected in the cursor. There will be a `RWTransaction.Flush()` function added in the future to flush the transaction to pages before writing to disk but cursors will be invalidated after this function is called.

3. Bidirectional cursors may be added later. I've never had much use for them but they're fairly easy to implement.

/cc: @snormore