xitdb

package module
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 28, 2026 License: MIT Imports: 10 Imported by: 0

README

xitdb is an immutable database written in Go

Choose your flavor: Zig | Java | Clojure | TypeScript | Go

  • Each transaction efficiently creates a new "copy" of the database, and past copies can still be read from and reverted to.
  • Supports storing in a single file as well as purely in-memory use.
  • Runs as a library (embedded in process).
  • Incrementally reads and writes, so file-based databases can contain larger-than-memory datasets.
  • Reads never block writes, and a database can be read from multiple threads/processes without locks.
  • No query engine of any kind. You just write data structures (primarily an ArrayList and HashMap) that can be nested arbitrarily.
  • No dependencies besides the Go standard library (requires Go 1.23+).

This database was originally made for the xit version control system, but I bet it has a lot of potential for other projects. The combination of being immutable and having an API similar to in-memory data structures is pretty powerful. Consider using it instead of SQLite for your Go projects: it's simpler, it's pure Go, and it creates no impedance mismatch with your program the way SQL databases do.

Example

In this example, we create a new database, write some data in a transaction, and read the data afterwards.

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

// init the db
core := xitdb.NewCoreBufferedFile(f)
hasher := xitdb.Hasher{Hash: sha1.New()}
db, err := xitdb.NewDatabase(core, hasher)
if err != nil {
    log.Fatal(err)
}

// to get the benefits of immutability, the top-level data structure
// must be an ArrayList, so each transaction is stored as an item in it
history, err := xitdb.NewWriteArrayList(db.RootCursor())
if err != nil {
    log.Fatal(err)
}

// this is how a transaction is executed. we call history.AppendContext,
// providing it with the most recent copy of the db and a context
// function. the function will run before the transaction has completed.
// this is where we can write changes to the db. if any error happens
// in it, the transaction will not complete and the db will be unaffected.
//
// after this transaction, the db will look like this if represented
// as JSON (in reality the format is binary):
//
// {"foo": "foo",
//  "bar": "bar",
//  "fruits": ["apple", "pear", "grape"],
//  "people": [
//    {"name": "Alice", "age": 25},
//    {"name": "Bob", "age": 42}
//  ]}
lastSlot, err := history.GetSlot(-1)
if err != nil {
    log.Fatal(err)
}
err = history.AppendContext(lastSlot, func(cursor *xitdb.WriteCursor) error {
    moment, err := xitdb.NewWriteHashMap(cursor)
    if err != nil {
        return err
    }

    if err := moment.Put("foo", xitdb.NewString("foo")); err != nil {
        return err
    }
    if err := moment.Put("bar", xitdb.NewString("bar")); err != nil {
        return err
    }

    fruitsCursor, err := moment.PutCursor("fruits")
    if err != nil {
        return err
    }
    fruits, err := xitdb.NewWriteArrayList(fruitsCursor)
    if err != nil {
        return err
    }
    if err := fruits.Append(xitdb.NewString("apple")); err != nil {
        return err
    }
    if err := fruits.Append(xitdb.NewString("pear")); err != nil {
        return err
    }
    if err := fruits.Append(xitdb.NewString("grape")); err != nil {
        return err
    }

    peopleCursor, err := moment.PutCursor("people")
    if err != nil {
        return err
    }
    people, err := xitdb.NewWriteArrayList(peopleCursor)
    if err != nil {
        return err
    }

    aliceCursor, err := people.AppendCursor()
    if err != nil {
        return err
    }
    alice, err := xitdb.NewWriteHashMap(aliceCursor)
    if err != nil {
        return err
    }
    if err := alice.Put("name", xitdb.NewString("Alice")); err != nil {
        return err
    }
    if err := alice.Put("age", xitdb.NewUint(25)); err != nil {
        return err
    }

    bobCursor, err := people.AppendCursor()
    if err != nil {
        return err
    }
    bob, err := xitdb.NewWriteHashMap(bobCursor)
    if err != nil {
        return err
    }
    if err := bob.Put("name", xitdb.NewString("Bob")); err != nil {
        return err
    }
    if err := bob.Put("age", xitdb.NewUint(42)); err != nil {
        return err
    }

    return nil
})
if err != nil {
    log.Fatal(err)
}

// get the most recent copy of the database, like a moment
// in time. the -1 index will return the last index in the list.
momentCursor, err := history.GetCursor(-1)
if err != nil {
    log.Fatal(err)
}
moment, err := xitdb.NewReadHashMap(momentCursor)
if err != nil {
    log.Fatal(err)
}

// we can read the value of "foo" from the map by getting
// the cursor to "foo" and then calling ReadBytes on it
fooCursor, err := moment.GetCursor("foo")
if err != nil {
    log.Fatal(err)
}
fooValue, err := fooCursor.ReadBytes(1024)
if err != nil {
    log.Fatal(err)
}
fmt.Println(string(fooValue)) // "foo"

// to get the "fruits" list, we get the cursor to it and
// then pass it to the ArrayList constructor
fruitsCursor, err := moment.GetCursor("fruits")
if err != nil {
    log.Fatal(err)
}
fruits, err := xitdb.NewReadArrayList(fruitsCursor)
if err != nil {
    log.Fatal(err)
}
fruitsCount, err := fruits.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(fruitsCount) // 3

// now we can get the first item from the fruits list and read it
appleCursor, err := fruits.GetCursor(0)
if err != nil {
    log.Fatal(err)
}
appleValue, err := appleCursor.ReadBytes(maxRead)
if err != nil {
    log.Fatal(err)
}
fmt.Println(string(appleValue)) // "apple"

Initializing a Database

A Database is initialized with an implementation of the Core interface, which determines how the i/o is done. There are three implementations of Core in this library: CoreBufferedFile, CoreFile, and CoreMemory.

  • CoreBufferedFile databases, like in the example above, write to a file while using an in-memory buffer to dramatically improve performance. This is highly recommended if you want to create a file-based database. Initialize with NewCoreBufferedFile(f) where f is an *os.File.
  • CoreFile databases use no buffering when reading and writing data. Initialize with NewCoreFile(f). This is almost never necessary but it's useful as a benchmark comparison with CoreBufferedFile databases.
  • CoreMemory databases work completely in memory. Initialize with NewCoreMemory().

Usually, you want to use a top-level ArrayList like in the example above, because that allows you to store a reference to each copy of the database (which I call a "moment"). This is how it supports transactions, despite not having any rollback journal or write-ahead log. It's an append-only database, so the data you are writing is invisible to any reader until the very last step, when the top-level list's header is updated.

You can also use a top-level HashMap, which is useful for ephemeral databases where immutability or transaction safety isn't necessary. Since xitdb supports in-memory databases, you could use it as an over-the-wire serialization format. Much like "Cap'n Proto", xitdb has no encoding/decoding step: you just give the buffer to xitdb and it can immediately read from it.

Types

In xitdb there are a variety of immutable data structures that you can nest arbitrarily:

  • HashMap contains key-value pairs stored with a hash
  • HashSet is like a HashMap that only sets the keys; it is useful when only checking for membership
  • CountedHashMap and CountedHashSet are just a HashMap and HashSet that maintain a count of their contents
  • ArrayList is a growable array
  • LinkedArrayList is like an ArrayList that can also be efficiently sliced and concatenated
  • SortedMap and SortedSet are like a HashMap and HashSet where the keys are byte arrays kept in lexicographic order

The Hash-based data structures and the Arraylist use the hash array mapped trie, invented by Phil Bagwell (originally made immutable and widely available by Rich Hickey in Clojure). The LinkedArrayList, SortedMap, and SortedSet are based on a B-tree.

There are also scalar types you can store in the above-mentioned data structures:

  • Bytes is a byte array
  • Uint is an unsigned 64-bit int
  • Int is a signed 64-bit int
  • Float is a 64-bit float

You may also want to define custom types. For example, you may want to store a big integer that can't fit in 64 bits. You could just store this with Bytes, but when reading the byte array there wouldn't be any indication that it should be interpreted as a big integer.

In xitdb, you can optionally store a format tag with a byte array. A format tag is a 2 byte tag that is stored alongside the byte array. Readers can use it to decide how to interpret the byte array. Here's an example of storing a random 256-bit number with bi as the format tag:

randomBigInt := make([]byte, 32)
rand.Read(randomBigInt)
if err := moment.Put("random-number", xitdb.NewTaggedBytes(randomBigInt, []byte("bi"))); err != nil {
    return err
}

Then, you can read it like this:

randomNumberCursor, err := moment.GetCursor("random-number")
if err != nil {
    log.Fatal(err)
}
randomNumber, err := randomNumberCursor.ReadBytesObject(1024)
if err != nil {
    log.Fatal(err)
}
fmt.Println(string(randomNumber.FormatTag)) // "bi"
bigInt := new(big.Int).SetBytes(randomNumber.Value)

There are many types you may want to store this way. Maybe an ISO-8601 date like 2026-01-01T18:55:48Z could be stored with dt as the format tag. It's also great for storing custom structs. Just define the struct, serialize it as a byte array using whatever mechanism you wish, and store it with a format tag. Keep in mind that format tags can be any 2 bytes, so there are 65536 possible format tags.

Cloning and Undoing

A powerful feature of immutable data is fast cloning. Any data structure can be instantly cloned and changed without affecting the original. Starting with the example code above, we can make a new transaction that creates a "food" list based on the existing "fruits" list:

lastSlot, err := history.GetSlot(-1)
if err != nil {
    log.Fatal(err)
}

err = history.AppendContext(lastSlot, func(cursor *xitdb.WriteCursor) error {
    moment, err := xitdb.NewWriteHashMap(cursor)
    if err != nil {
        return err
    }

    fruitsCursor, err := moment.GetCursor("fruits")
    if err != nil {
        return err
    }
    fruits, err := xitdb.NewReadArrayList(fruitsCursor)
    if err != nil {
        return err
    }

    // create a new key called "food" whose initial value is
    // based on the "fruits" list
    foodCursor, err := moment.PutCursor("food")
    if err != nil {
        return err
    }
    foodCursor.Write(fruits.Slot())

    food, err := xitdb.NewWriteArrayList(foodCursor)
    if err != nil {
        return err
    }
    if err := food.Append(xitdb.NewString("eggs")); err != nil {
        return err
    }
    if err := food.Append(xitdb.NewString("rice")); err != nil {
        return err
    }
    if err := food.Append(xitdb.NewString("fish")); err != nil {
        return err
    }

    return nil
})
if err != nil {
    log.Fatal(err)
}

momentCursor, err := history.GetCursor(-1)
if err != nil {
    log.Fatal(err)
}
moment, err := xitdb.NewReadHashMap(momentCursor)
if err != nil {
    log.Fatal(err)
}

// the food list includes the fruits
foodCursor, err := moment.GetCursor("food")
if err != nil {
    log.Fatal(err)
}
food, err := xitdb.NewReadArrayList(foodCursor)
if err != nil {
    log.Fatal(err)
}
foodCount, err := food.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(foodCount) // 6

// ...but the fruits list hasn't been changed
fruitsCursor, err := moment.GetCursor("fruits")
if err != nil {
    log.Fatal(err)
}
fruits, err := xitdb.NewReadArrayList(fruitsCursor)
if err != nil {
    log.Fatal(err)
}
fruitsCount, err := fruits.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(fruitsCount) // 3

Before we continue, let's save the latest history index, so we can revert back to this moment of the database later:

historyCount, err := history.Count()
if err != nil {
    log.Fatal(err)
}
historyIndex := historyCount - 1

There's one catch you'll run into when cloning. If we try cloning a data structure that was created in the same transaction, it doesn't seem to work:

lastSlot, err := history.GetSlot(-1)
if err != nil {
    log.Fatal(err)
}

err = history.AppendContext(lastSlot, func(cursor *xitdb.WriteCursor) error {
    moment, err := xitdb.NewWriteHashMap(cursor)
    if err != nil {
        return err
    }

    bigCitiesCursor, err := moment.PutCursor("big-cities")
    if err != nil {
        return err
    }
    bigCities, err := xitdb.NewWriteArrayList(bigCitiesCursor)
    if err != nil {
        return err
    }
    if err := bigCities.Append(xitdb.NewString("New York, NY")); err != nil {
        return err
    }
    if err := bigCities.Append(xitdb.NewString("Los Angeles, CA")); err != nil {
        return err
    }

    // create a new key called "cities" whose initial value is
    // based on the "big-cities" list
    citiesCursor, err := moment.PutCursor("cities")
    if err != nil {
        return err
    }
    citiesCursor.Write(bigCities.Slot())

    cities, err := xitdb.NewWriteArrayList(citiesCursor)
    if err != nil {
        return err
    }
    if err := cities.Append(xitdb.NewString("Charleston, SC")); err != nil {
        return err
    }
    if err := cities.Append(xitdb.NewString("Louisville, KY")); err != nil {
        return err
    }

    return nil
})
if err != nil {
    log.Fatal(err)
}

momentCursor, err := history.GetCursor(-1)
if err != nil {
    log.Fatal(err)
}
moment, err := xitdb.NewReadHashMap(momentCursor)
if err != nil {
    log.Fatal(err)
}

// the cities list contains all four
citiesCursor, err := moment.GetCursor("cities")
if err != nil {
    log.Fatal(err)
}
cities, err := xitdb.NewReadArrayList(citiesCursor)
if err != nil {
    log.Fatal(err)
}
citiesCount, err := cities.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(citiesCount) // 4

// ..but so does big-cities! we did not intend to mutate this
bigCitiesCursor, err := moment.GetCursor("big-cities")
if err != nil {
    log.Fatal(err)
}
bigCities, err := xitdb.NewReadArrayList(bigCitiesCursor)
if err != nil {
    log.Fatal(err)
}
bigCitiesCount, err := bigCities.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(bigCitiesCount) // 4

The reason that big-cities was mutated is because all data in a given transaction is temporarily mutable. This is a very important optimization, but in this case, it's not what we want.

To show how to fix this, let's first undo the transaction we just made. Here we use the historyIndex we saved before to revert back to the older database moment:

historySlot, err := history.GetSlot(historyIndex)
if err != nil {
    log.Fatal(err)
}
if err := history.Append(historySlot); err != nil {
    log.Fatal(err)
}

This time, after making the "big cities" list, we call Freeze, which tells xitdb to consider all data made so far in the transaction to be immutable. After that, we can clone it into the "cities" list and it will work the way we wanted:

lastSlot, err := history.GetSlot(-1)
if err != nil {
    log.Fatal(err)
}

err = history.AppendContext(lastSlot, func(cursor *xitdb.WriteCursor) error {
    moment, err := xitdb.NewWriteHashMap(cursor)
    if err != nil {
        return err
    }

    bigCitiesCursor, err := moment.PutCursor("big-cities")
    if err != nil {
        return err
    }
    bigCities, err := xitdb.NewWriteArrayList(bigCitiesCursor)
    if err != nil {
        return err
    }
    if err := bigCities.Append(xitdb.NewString("New York, NY")); err != nil {
        return err
    }
    if err := bigCities.Append(xitdb.NewString("Los Angeles, CA")); err != nil {
        return err
    }

    // freeze here, so big-cities won't be mutated
    if err := cursor.DB.Freeze(); err != nil {
        return err
    }

    // create a new key called "cities" whose initial value is
    // based on the "big-cities" list
    citiesCursor, err := moment.PutCursor("cities")
    if err != nil {
        return err
    }
    citiesCursor.Write(bigCities.Slot())

    cities, err := xitdb.NewWriteArrayList(citiesCursor)
    if err != nil {
        return err
    }
    if err := cities.Append(xitdb.NewString("Charleston, SC")); err != nil {
        return err
    }
    if err := cities.Append(xitdb.NewString("Louisville, KY")); err != nil {
        return err
    }

    return nil
})
if err != nil {
    log.Fatal(err)
}

momentCursor, err := history.GetCursor(-1)
if err != nil {
    log.Fatal(err)
}
moment, err := xitdb.NewReadHashMap(momentCursor)
if err != nil {
    log.Fatal(err)
}

// the cities list contains all four
citiesCursor, err := moment.GetCursor("cities")
if err != nil {
    log.Fatal(err)
}
cities, err := xitdb.NewReadArrayList(citiesCursor)
if err != nil {
    log.Fatal(err)
}
citiesCount, err := cities.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(citiesCount) // 4

// and big-cities only contains the original two
bigCitiesCursor, err := moment.GetCursor("big-cities")
if err != nil {
    log.Fatal(err)
}
bigCities, err := xitdb.NewReadArrayList(bigCitiesCursor)
if err != nil {
    log.Fatal(err)
}
bigCitiesCount, err := bigCities.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(bigCitiesCount) // 2

Sorting and Paginating

The Hash-based structures are great for looking data up by key, but they store their contents in hash order, which is meaningless to a human. You may need to display data in a sensible order (like newest posts first or users by signup date) and show it one page at a time. Relational databases like SQLite have this built-in: you declare a CREATE INDEX, write ORDER BY created_ts LIMIT 20 OFFSET 40, and the query planner maintains the index and seeks into it for you.

In xitdb there are no built-in indexes, so you build and maintain them yourself. That's a little more code, but the index is just another data structure: a SortedMap whose keys are crafted to sort the way you want. You keep it in sync by writing to it in the same transaction that writes the primary data.

Let's model the storage a basic blog would need: a collection of posts we look up by id, plus a secondary index that lets us list them oldest-first with pagination. The primary store is a HashMap from post id to the post's fields (like a row keyed by its primary key). The secondary index is a SortedMap keyed by creation time, whose value is the post id to look up.

The trick is the key. A SortedMap orders its keys lexicographically by their raw bytes, so we encode the timestamp as a big-endian integer (so byte order matches chronological order) and append the post id to break ties between posts created in the same second and keep every key unique:

// build a SortedMap key that sorts by creation time. the big-endian
// timestamp makes byte order match chronological order; the post id is
// appended so two posts with the same timestamp still get distinct keys.
func orderKey(timestamp uint64, postID []byte) []byte {
    key := make([]byte, 8+len(postID))
    binary.BigEndian.PutUint64(key[:8], timestamp)
    copy(key[8:], postID)
    return key
}

Now we write some posts. On each insert we write the post into the primary map and add an entry to the secondary index (keeping both in sync is your job, not the database's):

type Post struct {
    ID        string
    Title     string
    CreatedTs uint64
}

// post ids are fixed-length so the timestamp tie-breaker stays aligned
newPosts := []Post{
    {ID: "post000000000001", Title: "Hello, world", CreatedTs: 1_700_000_000},
    {ID: "post000000000002", Title: "Second post", CreatedTs: 1_700_000_500},
    {ID: "post000000000003", Title: "Third post", CreatedTs: 1_700_001_000},
}

lastSlot, err := history.GetSlot(-1)
if err != nil {
    log.Fatal(err)
}
err = history.AppendContext(lastSlot, func(cursor *xitdb.WriteCursor) error {
    moment, err := xitdb.NewWriteHashMap(cursor)
    if err != nil {
        return err
    }

    // the primary store: a HashMap from post id to the post's fields
    idToPostCursor, err := moment.PutCursor("id->post")
    if err != nil {
        return err
    }
    idToPost, err := xitdb.NewWriteHashMap(idToPostCursor)
    if err != nil {
        return err
    }

    // the secondary index: a SortedMap ordered by creation time. there's
    // no CREATE INDEX here, so we maintain it ourselves on every write.
    createdTsToPostIDCursor, err := moment.PutCursor("created-ts->post-id")
    if err != nil {
        return err
    }
    createdTsToPostID, err := xitdb.NewWriteSortedMap(createdTsToPostIDCursor)
    if err != nil {
        return err
    }

    for _, post := range newPosts {
        // write the post into the primary map under its id
        postCursor, err := idToPost.PutCursor(post.ID)
        if err != nil {
            return err
        }
        postMap, err := xitdb.NewWriteHashMap(postCursor)
        if err != nil {
            return err
        }
        if err := postMap.Put("title", xitdb.NewString(post.Title)); err != nil {
            return err
        }
        if err := postMap.Put("created-ts", xitdb.NewUint(post.CreatedTs)); err != nil {
            return err
        }

        // add an entry to the secondary index. the key sorts by time,
        // and the value is the post id we'll use to look the post back up.
        if err := createdTsToPostID.PutByBytes(orderKey(post.CreatedTs, []byte(post.ID)), xitdb.NewString(post.ID)); err != nil {
            return err
        }
    }
    return nil
})
if err != nil {
    log.Fatal(err)
}

To display a page, we walk the SortedMap instead of the HashMap. A web app would take a pageSize and an after offset from the request (something like /posts?after=20), so this is the xitdb equivalent of ORDER BY created_ts LIMIT pageSize OFFSET after:

momentCursor, err := history.GetCursor(-1)
if err != nil {
    log.Fatal(err)
}
moment, err := xitdb.NewReadHashMap(momentCursor)
if err != nil {
    log.Fatal(err)
}

idToPostCursor, err := moment.GetCursor("id->post")
if err != nil {
    log.Fatal(err)
}
idToPost, err := xitdb.NewReadHashMap(idToPostCursor)
if err != nil {
    log.Fatal(err)
}

createdTsToPostIDCursor, err := moment.GetCursor("created-ts->post-id")
if err != nil {
    log.Fatal(err)
}
createdTsToPostID, err := xitdb.NewReadSortedMap(createdTsToPostIDCursor)
if err != nil {
    log.Fatal(err)
}

// a web request would supply these; here we just grab the first page
pageSize := int64(2)
after := int64(0)

count, err := createdTsToPostID.Count()
if err != nil {
    log.Fatal(err)
}
end := after + pageSize
if end > count {
    end = count
}

// seek straight to the start of the page, then walk forward one entry at a
// time. because SortedMap is a count-augmented B+tree, AllFromIndex
// finds rank `after` in O(log n) without scanning the entries it skips, so
// jumping to page 500 is just as cheap as page 1.
i := after
for idCursor, err := range createdTsToPostID.AllFromIndex(after) {
    if err != nil {
        log.Fatal(err)
    }
    if i >= end {
        break
    }

    idKv, err := idCursor.ReadKeyValuePair()
    if err != nil {
        log.Fatal(err)
    }

    // the index entry's value is the post id; use it to read the
    // full post out of the primary map
    postIDBytes, err := idKv.ValueCursor.ReadBytes(1024)
    if err != nil {
        log.Fatal(err)
    }

    postCursor, err := idToPost.GetCursor(string(postIDBytes))
    if err != nil {
        log.Fatal(err)
    }
    postMap, err := xitdb.NewReadHashMap(postCursor)
    if err != nil {
        log.Fatal(err)
    }
    titleCursor, err := postMap.GetCursor("title")
    if err != nil {
        log.Fatal(err)
    }
    title, err := titleCursor.ReadBytes(1024)
    if err != nil {
        log.Fatal(err)
    }

    // a real app would render this into the page's HTML
    fmt.Println(string(title))

    i++
}

This works for any ordering you need: sort by a username with a string key, by score with a big-endian integer key, or build several SortedMap indexes over the same primary HashMap to offer the data in different orders. With xitdb you "bring your own index". It takes a bit more effort than the declarative convenience of SQL databases, but it gives you more explicit control, and avoids the common problem in SQL where queries silently become inefficient due to not using indexes. In xitdb, inefficiency is hard to miss because you are always writing your queries as imperative code and the indexes are always explicit.

Large Byte Arrays

When reading and writing large byte arrays, you probably don't want to have all of their contents in memory at once. To incrementally write to a byte array, just get a writer from a cursor:

longTextCursor, err := moment.PutCursor("long-text")
if err != nil {
    return err
}
cursorWriter, err := longTextCursor.Writer()
if err != nil {
    return err
}
bw := bufio.NewWriter(cursorWriter)
for i := 0; i < 50; i++ {
    bw.Write([]byte("hello, world\n"))
}
bw.Flush()
if err := cursorWriter.Finish(); err != nil {
    return err
}

If you need to set a format tag for the byte array, set the FormatTag field on the writer before you call Finish.

To read a byte array incrementally, get a reader from a cursor:

longTextCursor, err := moment.GetCursor("long-text")
if err != nil {
    log.Fatal(err)
}
cursorReader, err := longTextCursor.Reader()
if err != nil {
    log.Fatal(err)
}
scanner := bufio.NewScanner(cursorReader)
count := 0
for scanner.Scan() {
    count++
}
fmt.Println(count) // 50

Iterators

All data structures support iteration using Go 1.23's range-over-func iterators. Here's an example of iterating over an ArrayList and printing all of the keys and values of each HashMap contained in it:

peopleCursor, err := moment.GetCursor("people")
if err != nil {
    log.Fatal(err)
}
people, err := xitdb.NewReadArrayList(peopleCursor)
if err != nil {
    log.Fatal(err)
}

for personCursor, err := range people.All() {
    if err != nil {
        log.Fatal(err)
    }
    person, err := xitdb.NewReadHashMap(personCursor)
    if err != nil {
        log.Fatal(err)
    }

    for kvPairCursor, err := range person.All() {
        if err != nil {
            log.Fatal(err)
        }
        kvPair, err := kvPairCursor.ReadKeyValuePair()
        if err != nil {
            log.Fatal(err)
        }

        key, err := kvPair.KeyCursor.ReadBytes(1024)
        if err != nil {
            log.Fatal(err)
        }

        switch kvPair.ValueCursor.SlotPtr.Slot.Tag {
        case xitdb.TagShortBytes, xitdb.TagBytes:
            val, err := kvPair.ValueCursor.ReadBytes(1024)
            if err != nil {
                log.Fatal(err)
            }
            fmt.Printf("%s: %s\n", key, val)
        case xitdb.TagUint:
            val, err := kvPair.ValueCursor.ReadUint()
            if err != nil {
                log.Fatal(err)
            }
            fmt.Printf("%s: %d\n", key, val)
        case xitdb.TagInt:
            val, err := kvPair.ValueCursor.ReadInt()
            if err != nil {
                log.Fatal(err)
            }
            fmt.Printf("%s: %d\n", key, val)
        case xitdb.TagFloat:
            val, err := kvPair.ValueCursor.ReadFloat()
            if err != nil {
                log.Fatal(err)
            }
            fmt.Printf("%s: %f\n", key, val)
        }
    }
}

The above code iterates over people, which is an ArrayList, and for each person (which is a HashMap), it iterates over each of its key-value pairs.

The iteration of the HashMap looks the same with HashSet, CountedHashMap, and CountedHashSet. When iterating, you call ReadKeyValuePair on the cursor and can read the KeyCursor and ValueCursor from it. In maps, Put sets the key and value. In sets, Put only sets the key; the value will always have a tag type of TagNone.

ArrayList and LinkedArrayList also have an AllFrom method, which starts the iterator from the given index. SortedMap and SortedSet have AllFrom and AllFromIndex to start the iterator from a key or index respectively. This is especially useful for pagination: you can seek straight to the start of a page and walk forward only as far as you need. See the Sorting and Paginating section for an example.

Hashing

The hashing data structures will create the hash for you when you call methods like Put or GetCursor. If you want to do the hashing yourself, there are methods like PutByHash and GetCursorByHash that take a []byte as the hash.

When initializing a database, you tell xitdb how to hash with the Hasher. If you're using SHA-1, it will look like this:

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

core := xitdb.NewCoreFile(f)
hasher := xitdb.Hasher{Hash: sha1.New()}
db, err := xitdb.NewDatabase(core, hasher)
if err != nil {
    log.Fatal(err)
}

The size of the hash in bytes will be stored in the database's header. If you try opening it later with a hashing algorithm that has the wrong hash size, it will return an error. If you are unsure what hash size the database uses, this creates a chicken-and-egg problem. You can read the header before initializing the database like this:

if err := core.SeekTo(0); err != nil {
    log.Fatal(err)
}
header, err := xitdb.ReadHeader(core)
if err != nil {
    log.Fatal(err)
}
fmt.Println(header.HashSize) // 20

The hash size alone does not disambiguate hashing algorithms, though. In addition, xitdb reserves four bytes in the header that you can use to put the name of the algorithm. You must provide it in the Hasher:

hasher := xitdb.Hasher{
    Hash: sha1.New(),
    ID:   xitdb.BytesToID([4]byte{'s', 'h', 'a', '1'}),
}

The hash id is only written to the database header when it is first initialized. When you open it later, the hash id in the Hasher is ignored. You can read the hash id of an existing database like this:

if err := core.SeekTo(0); err != nil {
    log.Fatal(err)
}
header, err := xitdb.ReadHeader(core)
if err != nil {
    log.Fatal(err)
}
fmt.Println(xitdb.IDToBytes(header.HashID)) // [4]byte{'s', 'h', 'a', '1'}

If you want to use SHA-256, I recommend using sha2 as the hash id. You can then distinguish between SHA-256 and SHA-512 using the hash size, like this:

if err := core.SeekTo(0); err != nil {
    log.Fatal(err)
}
header, err := xitdb.ReadHeader(core)
if err != nil {
    log.Fatal(err)
}

var hasher xitdb.Hasher
switch xitdb.IDToBytes(header.HashID) {
case [4]byte{'s', 'h', 'a', '1'}:
    hasher = xitdb.Hasher{
        Hash: sha1.New(),
        ID:   header.HashID,
    }
case [4]byte{'s', 'h', 'a', '2'}:
    switch header.HashSize {
    case 32:
        hasher = xitdb.Hasher{
            Hash: sha256.New(),
            ID:   header.HashID,
        }
    case 64:
        hasher = xitdb.Hasher{
            Hash: sha512.New(),
            ID:   header.HashID,
        }
    default:
        log.Fatal("Invalid hash size")
    }
default:
    log.Fatal("Invalid hash algorithm")
}

Compaction

Normally, an immutable database grows forever, because old data is never deleted. To reclaim disk space and clear the history, xitdb supports compaction. This involves completely rebuilding the database file to only contain the data accessible from the latest copy (i.e., "moment") of the database.

compactFile, err := os.OpenFile("compact.db", os.O_RDWR|os.O_CREATE, 0644)
if err != nil {
    log.Fatal(err)
}
defer compactFile.Close()

compactCore := xitdb.NewCoreBufferedFile(compactFile)
compactDb, err := db.Compact(compactCore)
if err != nil {
    log.Fatal(err)
}

// read from the new compacted db
history, err := xitdb.NewReadArrayList(compactDb.RootCursor().ReadCursor)
if err != nil {
    log.Fatal(err)
}
historyCount, err := history.Count()
if err != nil {
    log.Fatal(err)
}
fmt.Println(historyCount) // 1

This compacted database will be in a separate file. If you want to delete the original database and replace it with this one, you'll need to do that yourself. It is not possible to compact a database in-place (using the same file as the target database); doing so would fail and would render your original database unreadable.

Thread Safety

It is possible to read the database from multiple threads/goroutines without locks, even while writes are happening. This is a big benefit of immutable databases. However, each thread needs to use its own Database instance. See the multithreading test for an example of this. Also, keep in mind that writes still need to come from one thread at a time.

Documentation

Index

Constants

View Source 
const (
	Version         uint16 = 0
	DatabaseStart          = HeaderLength
	BitCount               = 4
	SlotCount              = 1 << BitCount
	Mask            int64  = SlotCount - 1
	IndexBlockSize         = SlotLength * SlotCount
	MaxBranchLength        = 16
	// b-tree (backs LinkedArrayList): nodes hold up to BTreeSlotCount entries
	BTreeSlotCount       = SlotCount
	BTreeSplitCount      = (BTreeSlotCount + 1) / 2
	BTreeNodeHeaderSize  = 2
	BTreeLeafBlockSize   = BTreeNodeHeaderSize + SlotLength*BTreeSlotCount
	BTreeBranchBlockSize = BTreeNodeHeaderSize + (SlotLength+8)*BTreeSlotCount
	// sorted_map / sorted_set node block: a leaf holds BTreeSlotCount kv_pair slots;
	// a branch holds child slots, separator slots, then BTreeSlotCount u64 counts
	SortedLeafBlockSize   = BTreeNodeHeaderSize + SlotLength*BTreeSlotCount
	SortedBranchBlockSize = BTreeNodeHeaderSize + (SlotLength*2+8)*BTreeSlotCount
)
View Source 
const ArrayListHeaderLength = 16
View Source 
const BTreeHeaderLength = 16
View Source 
const HeaderLength = 12
View Source 
const SlotLength = 9
View Source 
const TopLevelArrayListHeaderLength = 8 + ArrayListHeaderLength

Variables

View Source 
var (
	MagicNumber = [3]byte{'x', 'i', 't'}
	BigMask     = big.NewInt(Mask)
)
View Source 
var (
	ErrInvalidDatabase          = errors.New("invalid database")
	ErrInvalidVersion           = errors.New("invalid version")
	ErrInvalidHashSize          = errors.New("invalid hash size")
	ErrKeyNotFound              = errors.New("key not found")
	ErrWriteNotAllowed          = errors.New("write not allowed")
	ErrUnexpectedTag            = errors.New("unexpected tag")
	ErrCursorNotWriteable       = errors.New("cursor not writeable")
	ErrExpectedTxStart          = errors.New("expected tx start")
	ErrKeyOffsetExceeded        = errors.New("key offset exceeded")
	ErrPathPartMustBeAtEnd      = errors.New("path part must be at end")
	ErrStreamTooLong            = errors.New("stream too long")
	ErrEndOfStream              = errors.New("end of stream")
	ErrInvalidOffset            = errors.New("invalid offset")
	ErrInvalidTopLevelType      = errors.New("invalid top level type")
	ErrExpectedUnsignedLong     = errors.New("expected unsigned long")
	ErrNoAvailableSlots         = errors.New("no available slots")
	ErrMustSetNewSlotsToFull    = errors.New("must set new slots to full")
	ErrEmptySlot                = errors.New("empty slot")
	ErrExpectedRootNode         = errors.New("expected root node")
	ErrInvalidFormatTagSize     = errors.New("invalid format tag size")
	ErrUnexpectedWriterPosition = errors.New("unexpected writer position")
	ErrMaxShiftExceeded         = errors.New("max shift exceeded")
	ErrInvalidBTreeNode         = errors.New("invalid btree node")
	ErrInvalidBTreeNodeKind     = errors.New("invalid btree node kind")
	ErrNotImplemented           = errors.New("not implemented")
	ErrUnreachable              = errors.New("unreachable")
)

Functions

func BytesToID 

func BytesToID(name [4]byte) uint32

func IDToBytes 

func IDToBytes(id uint32) [4]byte

func KeyValuePairLength 

func KeyValuePairLength(hashSize int) int

Types

type ArrayListAppend 

type ArrayListAppend struct{}

type ArrayListAppendResult 

type ArrayListAppendResult struct {
	Header  ArrayListHeader
	SlotPtr SlotPointer
}

type ArrayListGet 

type ArrayListGet struct {
	Index int64
}

type ArrayListHeader 

type ArrayListHeader struct {
	Ptr  int64
	Size int64
}

func ArrayListHeaderFromBytes 

func ArrayListHeaderFromBytes(b []byte) (ArrayListHeader, error)

func (ArrayListHeader) ToBytes 

func (h ArrayListHeader) ToBytes() [ArrayListHeaderLength]byte

func (ArrayListHeader) WithPtr 

func (h ArrayListHeader) WithPtr(ptr int64) ArrayListHeader

type ArrayListInit 

type ArrayListInit struct{}

type ArrayListSlice 

type ArrayListSlice struct {
	Size int64
}

type BTreeHeader added in v0.2.0 

type BTreeHeader struct {
	RootPtr int64
	Size    int64
}

func BTreeHeaderFromBytes added in v0.2.0 

func BTreeHeaderFromBytes(b []byte) (BTreeHeader, error)

func (BTreeHeader) ToBytes added in v0.2.0 

func (h BTreeHeader) ToBytes() [BTreeHeaderLength]byte

type BTreeInsertResult added in v0.2.0 

type BTreeInsertResult struct {
	NodePtr       int64
	Count         int64
	ValuePosition int64
	Split         *BTreeNodeRef
}

type BTreeJoinResult added in v0.2.0 

type BTreeJoinResult struct {
	NodePtr int64
	Count   int64
	Split   *BTreeNodeRef
}

type BTreeNode added in v0.2.0 

type BTreeNode struct {
	Kind     BTreeNodeKind
	Num      int
	Values   [BTreeSlotCount]Slot  // leaf
	Children [BTreeSlotCount]Slot  // branch
	Counts   [BTreeSlotCount]int64 // branch
}

func (*BTreeNode) SubtreeCount added in v0.2.0 

func (n *BTreeNode) SubtreeCount() int64

type BTreeNodeKind added in v0.2.0 

type BTreeNodeKind byte
const (
	BTreeKindLeaf   BTreeNodeKind = 0
	BTreeKindBranch BTreeNodeKind = 1
)

type BTreeNodeRef added in v0.2.0 

type BTreeNodeRef struct {
	NodePtr int64
	Count   int64
}

a node pointer plus the element count of its subtree (the right sibling of a split)

type BTreeSplitResult added in v0.2.0 

type BTreeSplitResult struct {
	Left  int64
	Right int64
}

type BTreeWriteSlot added in v0.2.0 

type BTreeWriteSlot struct {
	NodePtr       int64
	ValuePosition int64
	Slot          Slot
}

type Bytes 

type Bytes struct {
	Value     []byte
	FormatTag []byte
}

func NewBytes 

func NewBytes(value []byte) Bytes

func NewString 

func NewString(value string) Bytes

func NewTaggedBytes 

func NewTaggedBytes(value []byte, formatTag []byte) Bytes

func NewTaggedString 

func NewTaggedString(value string, formatTag string) Bytes

func (Bytes) IsShort 

func (b Bytes) IsShort() bool

type Context 

type Context struct {
	Function ContextFunction
}

type ContextFunction 

type ContextFunction func(cursor *WriteCursor) error

type Core 

type Core interface {
	Read(p []byte) error
	Write(p []byte) error
	Length() (int64, error)
	SeekTo(pos int64) error
	Position() (int64, error)
	SetLength(len int64) error
	Flush() error
	Sync() error
}

type CoreBufferedFile 

type CoreBufferedFile struct {
	// contains filtered or unexported fields
}

func NewCoreBufferedFile 

func NewCoreBufferedFile(f *os.File) *CoreBufferedFile

func NewCoreBufferedFileWithSize 

func NewCoreBufferedFileWithSize(f *os.File, bufferSize int) *CoreBufferedFile

func (*CoreBufferedFile) Close 

func (c *CoreBufferedFile) Close() error

func (*CoreBufferedFile) Flush 

func (c *CoreBufferedFile) Flush() error

func (*CoreBufferedFile) Length 

func (c *CoreBufferedFile) Length() (int64, error)

func (*CoreBufferedFile) Position 

func (c *CoreBufferedFile) Position() (int64, error)

func (*CoreBufferedFile) Read 

func (c *CoreBufferedFile) Read(p []byte) error

func (*CoreBufferedFile) SeekTo 

func (c *CoreBufferedFile) SeekTo(pos int64) error

func (*CoreBufferedFile) SetLength 

func (c *CoreBufferedFile) SetLength(length int64) error

func (*CoreBufferedFile) Sync 

func (c *CoreBufferedFile) Sync() error

func (*CoreBufferedFile) Write 

func (c *CoreBufferedFile) Write(p []byte) error

type CoreFile 

type CoreFile struct {
	File *os.File
}

func NewCoreFile 

func NewCoreFile(f *os.File) *CoreFile

func (*CoreFile) Flush 

func (c *CoreFile) Flush() error

func (*CoreFile) Length 

func (c *CoreFile) Length() (int64, error)

func (*CoreFile) Position 

func (c *CoreFile) Position() (int64, error)

func (*CoreFile) Read 

func (c *CoreFile) Read(p []byte) error

func (*CoreFile) SeekTo 

func (c *CoreFile) SeekTo(pos int64) error

func (*CoreFile) SetLength 

func (c *CoreFile) SetLength(length int64) error

func (*CoreFile) Sync 

func (c *CoreFile) Sync() error

func (*CoreFile) Write 

func (c *CoreFile) Write(p []byte) error

type CoreMemory 

type CoreMemory struct {
	// contains filtered or unexported fields
}

func NewCoreMemory 

func NewCoreMemory() *CoreMemory

func (*CoreMemory) Flush 

func (m *CoreMemory) Flush() error

func (*CoreMemory) Length 

func (m *CoreMemory) Length() (int64, error)

func (*CoreMemory) Position 

func (m *CoreMemory) Position() (int64, error)

func (*CoreMemory) Read 

func (m *CoreMemory) Read(p []byte) error

func (*CoreMemory) SeekTo 

func (m *CoreMemory) SeekTo(pos int64) error

func (*CoreMemory) SetLength 

func (m *CoreMemory) SetLength(length int64) error

func (*CoreMemory) Sync 

func (m *CoreMemory) Sync() error

func (*CoreMemory) Write 

func (m *CoreMemory) Write(p []byte) error

type CursorIterator 

type CursorIterator struct {
	// contains filtered or unexported fields
}

type CursorReader 

type CursorReader struct {
	// contains filtered or unexported fields
}

func (*CursorReader) Read 

func (r *CursorReader) Read(p []byte) (int, error)

func (*CursorReader) ReadAll 

func (r *CursorReader) ReadAll() ([]byte, error)

func (*CursorReader) ReadByte 

func (r *CursorReader) ReadByte() (byte, error)

func (*CursorReader) ReadFully 

func (r *CursorReader) ReadFully(buf []byte) error

func (*CursorReader) ReadInt32 

func (r *CursorReader) ReadInt32() (int32, error)

func (*CursorReader) ReadLong 

func (r *CursorReader) ReadLong() (int64, error)

func (*CursorReader) ReadShort 

func (r *CursorReader) ReadShort() (int16, error)

func (*CursorReader) SeekTo 

func (r *CursorReader) SeekTo(position int64) error

type CursorWriter 

type CursorWriter struct {
	FormatTag []byte
	// contains filtered or unexported fields
}

func (*CursorWriter) Finish 

func (w *CursorWriter) Finish() error

func (*CursorWriter) SeekTo 

func (w *CursorWriter) SeekTo(position int64)

func (*CursorWriter) Write 

func (w *CursorWriter) Write(p []byte) (int, error)

type Database 

type Database struct {
	Core Core

	Header  Header
	TxStart *int64
	// contains filtered or unexported fields
}

func NewDatabase 

func NewDatabase(core Core, hasher Hasher) (*Database, error)

func (*Database) Compact 

func (db *Database) Compact(targetCore Core) (*Database, error)

func (*Database) Freeze 

func (db *Database) Freeze() error

func (*Database) RootCursor 

func (db *Database) RootCursor() *WriteCursor

type Float 

type Float struct {
	Value float64
}

func NewFloat 

func NewFloat(value float64) Float

type HashMapGetKVPair 

type HashMapGetKVPair struct{ Hash []byte }

type HashMapGetKey 

type HashMapGetKey struct{ Hash []byte }

type HashMapGetPart 

type HashMapGetPart struct {
	Target HashMapGetTarget
}

type HashMapGetResult 

type HashMapGetResult struct {
	SlotPtr SlotPointer
	IsEmpty bool
}

type HashMapGetTarget 

type HashMapGetTarget interface {
	// contains filtered or unexported methods
}

type HashMapGetValue 

type HashMapGetValue struct{ Hash []byte }

type HashMapInitPart 

type HashMapInitPart struct {
	Counted bool
	Set     bool
}

type HashMapRemovePart 

type HashMapRemovePart struct {
	Hash []byte
}

type Hasher 

type Hasher struct {
	Hash hash.Hash
	ID   uint32
}
type Header struct {
	HashID      uint32
	HashSize    uint16
	Version     uint16
	Tag         Tag
	MagicNumber [3]byte
}

func ReadHeader 

func ReadHeader(c Core) (Header, error)

func (Header) ToBytes 

func (h Header) ToBytes() [HeaderLength]byte

func (Header) Validate 

func (h Header) Validate() error

func (Header) WithTag 

func (h Header) WithTag(tag Tag) Header

func (Header) Write 

func (h Header) Write(c Core) error

type Int 

type Int struct {
	Value int64
}

func NewInt 

func NewInt(value int64) Int

type KeyValuePair 

type KeyValuePair struct {
	ValueSlot Slot
	KeySlot   Slot
	Hash      []byte
}

func KeyValuePairFromBytes 

func KeyValuePairFromBytes(b []byte, hashSize int) KeyValuePair

func (KeyValuePair) ToBytes 

func (kvp KeyValuePair) ToBytes() []byte

type LinkedArrayListAppend 

type LinkedArrayListAppend struct{}

type LinkedArrayListConcatPart 

type LinkedArrayListConcatPart struct {
	List Slot
}

type LinkedArrayListGet 

type LinkedArrayListGet struct {
	Index int64
}

type LinkedArrayListInit 

type LinkedArrayListInit struct{}

type LinkedArrayListInsertPart 

type LinkedArrayListInsertPart struct {
	Index int64
}

type LinkedArrayListRemovePart 

type LinkedArrayListRemovePart struct {
	Index int64
}

type LinkedArrayListSlicePart 

type LinkedArrayListSlicePart struct {
	Offset int64
	Size   int64
}

type PathPart 

type PathPart interface {
	// contains filtered or unexported methods
}

type ReadArrayList 

type ReadArrayList struct {
	Cursor *ReadCursor
}

func NewReadArrayList 

func NewReadArrayList(cursor *ReadCursor) (*ReadArrayList, error)

func (*ReadArrayList) All 

func (a *ReadArrayList) All() iter.Seq2[*ReadCursor, error]

func (*ReadArrayList) AllFrom added in v0.4.0 

func (a *ReadArrayList) AllFrom(index int64) iter.Seq2[*ReadCursor, error]

AllFrom iterates starting at the given index, seeking straight to it instead of walking from the front. negative indexes count from the end.

func (*ReadArrayList) Count 

func (a *ReadArrayList) Count() (int64, error)

func (*ReadArrayList) GetCursor 

func (a *ReadArrayList) GetCursor(index int64) (*ReadCursor, error)

func (*ReadArrayList) GetSlot 

func (a *ReadArrayList) GetSlot(index int64) (Slot, error)

func (*ReadArrayList) Slot 

func (a *ReadArrayList) Slot() Slot

type ReadCountedHashMap 

type ReadCountedHashMap struct {
	*ReadHashMap
}

func NewReadCountedHashMap 

func NewReadCountedHashMap(cursor *ReadCursor) (*ReadCountedHashMap, error)

func (*ReadCountedHashMap) Count 

func (m *ReadCountedHashMap) Count() (int64, error)

type ReadCountedHashSet 

type ReadCountedHashSet struct {
	*ReadHashSet
}

func NewReadCountedHashSet 

func NewReadCountedHashSet(cursor *ReadCursor) (*ReadCountedHashSet, error)

func (*ReadCountedHashSet) Count 

func (s *ReadCountedHashSet) Count() (int64, error)

type ReadCursor 

type ReadCursor struct {
	SlotPtr SlotPointer
	DB      *Database
}

func (*ReadCursor) All 

func (c *ReadCursor) All() iter.Seq2[*ReadCursor, error]

func (*ReadCursor) Count 

func (c *ReadCursor) Count() (int64, error)

func (*ReadCursor) ReadBytes 

func (c *ReadCursor) ReadBytes(maxSize int64) ([]byte, error)

func (*ReadCursor) ReadBytesObject 

func (c *ReadCursor) ReadBytesObject(maxSize int64) (Bytes, error)

func (*ReadCursor) ReadFloat 

func (c *ReadCursor) ReadFloat() (float64, error)

func (*ReadCursor) ReadInt 

func (c *ReadCursor) ReadInt() (int64, error)

func (*ReadCursor) ReadKeyValuePair 

func (c *ReadCursor) ReadKeyValuePair() (*ReadKVPairCursor, error)

func (*ReadCursor) ReadPath 

func (c *ReadCursor) ReadPath(path []PathPart) (*ReadCursor, error)

func (*ReadCursor) ReadPathSlot 

func (c *ReadCursor) ReadPathSlot(path []PathPart) (Slot, error)

func (*ReadCursor) ReadUint 

func (c *ReadCursor) ReadUint() (uint64, error)

func (*ReadCursor) Reader 

func (c *ReadCursor) Reader() (*CursorReader, error)

func (*ReadCursor) Slot 

func (c *ReadCursor) Slot() Slot

type ReadHashMap 

type ReadHashMap struct {
	Cursor *ReadCursor
}

func NewReadHashMap 

func NewReadHashMap(cursor *ReadCursor) (*ReadHashMap, error)

func (*ReadHashMap) All 

func (m *ReadHashMap) All() iter.Seq2[*ReadCursor, error]

func (*ReadHashMap) GetCursor 

func (m *ReadHashMap) GetCursor(key string) (*ReadCursor, error)

func (*ReadHashMap) GetCursorByBytes 

func (m *ReadHashMap) GetCursorByBytes(key Bytes) (*ReadCursor, error)

func (*ReadHashMap) GetCursorByHash 

func (m *ReadHashMap) GetCursorByHash(hash []byte) (*ReadCursor, error)

func (*ReadHashMap) GetKeyCursor 

func (m *ReadHashMap) GetKeyCursor(key string) (*ReadCursor, error)

func (*ReadHashMap) GetKeyCursorByBytes 

func (m *ReadHashMap) GetKeyCursorByBytes(key Bytes) (*ReadCursor, error)

func (*ReadHashMap) GetKeyCursorByHash 

func (m *ReadHashMap) GetKeyCursorByHash(hash []byte) (*ReadCursor, error)

func (*ReadHashMap) GetKeySlot 

func (m *ReadHashMap) GetKeySlot(key string) (Slot, error)

func (*ReadHashMap) GetKeySlotByBytes 

func (m *ReadHashMap) GetKeySlotByBytes(key Bytes) (Slot, error)

func (*ReadHashMap) GetKeySlotByHash 

func (m *ReadHashMap) GetKeySlotByHash(hash []byte) (Slot, error)

func (*ReadHashMap) GetKeyValuePair 

func (m *ReadHashMap) GetKeyValuePair(key string) (*ReadKVPairCursor, error)

func (*ReadHashMap) GetKeyValuePairByBytes 

func (m *ReadHashMap) GetKeyValuePairByBytes(key Bytes) (*ReadKVPairCursor, error)

func (*ReadHashMap) GetKeyValuePairByHash 

func (m *ReadHashMap) GetKeyValuePairByHash(hash []byte) (*ReadKVPairCursor, error)

func (*ReadHashMap) GetSlot 

func (m *ReadHashMap) GetSlot(key string) (Slot, error)

func (*ReadHashMap) GetSlotByBytes 

func (m *ReadHashMap) GetSlotByBytes(key Bytes) (Slot, error)

func (*ReadHashMap) GetSlotByHash 

func (m *ReadHashMap) GetSlotByHash(hash []byte) (Slot, error)

func (*ReadHashMap) Slot 

func (m *ReadHashMap) Slot() Slot

type ReadHashSet 

type ReadHashSet struct {
	Cursor *ReadCursor
}

func NewReadHashSet 

func NewReadHashSet(cursor *ReadCursor) (*ReadHashSet, error)

func (*ReadHashSet) All 

func (s *ReadHashSet) All() iter.Seq2[*ReadCursor, error]

func (*ReadHashSet) GetCursor 

func (s *ReadHashSet) GetCursor(key string) (*ReadCursor, error)

func (*ReadHashSet) GetCursorByBytes 

func (s *ReadHashSet) GetCursorByBytes(key Bytes) (*ReadCursor, error)

func (*ReadHashSet) GetCursorByHash 

func (s *ReadHashSet) GetCursorByHash(hash []byte) (*ReadCursor, error)

func (*ReadHashSet) GetSlot 

func (s *ReadHashSet) GetSlot(key string) (Slot, error)

func (*ReadHashSet) GetSlotByBytes 

func (s *ReadHashSet) GetSlotByBytes(key Bytes) (Slot, error)

func (*ReadHashSet) GetSlotByHash 

func (s *ReadHashSet) GetSlotByHash(hash []byte) (Slot, error)

func (*ReadHashSet) Slot 

func (s *ReadHashSet) Slot() Slot

type ReadKVPairCursor 

type ReadKVPairCursor struct {
	ValueCursor *ReadCursor
	KeyCursor   *ReadCursor
	Hash        []byte
}

type ReadLinkedArrayList 

type ReadLinkedArrayList struct {
	Cursor *ReadCursor
}

func NewReadLinkedArrayList 

func NewReadLinkedArrayList(cursor *ReadCursor) (*ReadLinkedArrayList, error)

func (*ReadLinkedArrayList) All 

func (a *ReadLinkedArrayList) All() iter.Seq2[*ReadCursor, error]

func (*ReadLinkedArrayList) AllFrom added in v0.4.0 

func (a *ReadLinkedArrayList) AllFrom(index int64) iter.Seq2[*ReadCursor, error]

AllFrom iterates starting at the given index, seeking straight to it instead of walking from the front. negative indexes count from the end.

func (*ReadLinkedArrayList) Count 

func (a *ReadLinkedArrayList) Count() (int64, error)

func (*ReadLinkedArrayList) GetCursor 

func (a *ReadLinkedArrayList) GetCursor(index int64) (*ReadCursor, error)

func (*ReadLinkedArrayList) GetSlot 

func (a *ReadLinkedArrayList) GetSlot(index int64) (Slot, error)

func (*ReadLinkedArrayList) Slot 

func (a *ReadLinkedArrayList) Slot() Slot

type ReadSortedMap added in v0.2.0 

type ReadSortedMap struct {
	Cursor *ReadCursor
}

func NewReadSortedMap added in v0.2.0 

func NewReadSortedMap(cursor *ReadCursor) (*ReadSortedMap, error)

func (*ReadSortedMap) All added in v0.2.0 

func (m *ReadSortedMap) All() iter.Seq2[*ReadCursor, error]

func (*ReadSortedMap) AllFrom added in v0.4.0 

func (m *ReadSortedMap) AllFrom(startKey []byte) iter.Seq2[*ReadCursor, error]

AllFrom iterates in key order starting at the first entry with key >= startKey

func (*ReadSortedMap) AllFromIndex added in v0.4.0 

func (m *ReadSortedMap) AllFromIndex(startIndex int64) iter.Seq2[*ReadCursor, error]

AllFromIndex iterates in key order starting at the entry with rank startIndex

func (*ReadSortedMap) Count added in v0.2.0 

func (m *ReadSortedMap) Count() (int64, error)

func (*ReadSortedMap) GetCursor added in v0.2.0 

func (m *ReadSortedMap) GetCursor(key string) (*ReadCursor, error)

func (*ReadSortedMap) GetCursorByBytes added in v0.2.0 

func (m *ReadSortedMap) GetCursorByBytes(key []byte) (*ReadCursor, error)

func (*ReadSortedMap) GetIndexKeyValuePair added in v0.2.0 

func (m *ReadSortedMap) GetIndexKeyValuePair(index int64) (*ReadKVPairCursor, error)

GetIndexKeyValuePair returns the key/value pair at the given rank (negative counts from the end)

func (*ReadSortedMap) GetKeyValuePair added in v0.2.0 

func (m *ReadSortedMap) GetKeyValuePair(key string) (*ReadKVPairCursor, error)

func (*ReadSortedMap) GetKeyValuePairByBytes added in v0.2.0 

func (m *ReadSortedMap) GetKeyValuePairByBytes(key []byte) (*ReadKVPairCursor, error)

func (*ReadSortedMap) GetSlot added in v0.2.0 

func (m *ReadSortedMap) GetSlot(key string) (Slot, error)

func (*ReadSortedMap) GetSlotByBytes added in v0.2.0 

func (m *ReadSortedMap) GetSlotByBytes(key []byte) (Slot, error)

func (*ReadSortedMap) Rank added in v0.2.0 

func (m *ReadSortedMap) Rank(key string) (int64, error)

func (*ReadSortedMap) RankByBytes added in v0.2.0 

func (m *ReadSortedMap) RankByBytes(key []byte) (int64, error)

RankByBytes returns the number of keys strictly less than key

func (*ReadSortedMap) Slot added in v0.2.0 

func (m *ReadSortedMap) Slot() Slot

type ReadSortedSet added in v0.2.0 

type ReadSortedSet struct {
	Cursor *ReadCursor
}

func NewReadSortedSet added in v0.2.0 

func NewReadSortedSet(cursor *ReadCursor) (*ReadSortedSet, error)

func (*ReadSortedSet) All added in v0.2.0 

func (s *ReadSortedSet) All() iter.Seq2[*ReadCursor, error]

func (*ReadSortedSet) AllFrom added in v0.4.0 

func (s *ReadSortedSet) AllFrom(startKey []byte) iter.Seq2[*ReadCursor, error]

func (*ReadSortedSet) AllFromIndex added in v0.4.0 

func (s *ReadSortedSet) AllFromIndex(startIndex int64) iter.Seq2[*ReadCursor, error]

func (*ReadSortedSet) Contains added in v0.2.0 

func (s *ReadSortedSet) Contains(key string) (bool, error)

func (*ReadSortedSet) ContainsByBytes added in v0.2.0 

func (s *ReadSortedSet) ContainsByBytes(key []byte) (bool, error)

func (*ReadSortedSet) Count added in v0.2.0 

func (s *ReadSortedSet) Count() (int64, error)

func (*ReadSortedSet) GetIndexKeyValuePair added in v0.2.0 

func (s *ReadSortedSet) GetIndexKeyValuePair(index int64) (*ReadKVPairCursor, error)

GetIndexKeyValuePair returns the key/value pair at the given rank (negative counts from the end)

func (*ReadSortedSet) Rank added in v0.2.0 

func (s *ReadSortedSet) Rank(key string) (int64, error)

func (*ReadSortedSet) RankByBytes added in v0.2.0 

func (s *ReadSortedSet) RankByBytes(key []byte) (int64, error)

RankByBytes returns the number of keys strictly less than key

func (*ReadSortedSet) Slot added in v0.2.0 

func (s *ReadSortedSet) Slot() Slot

type Slot 

type Slot struct {
	Value int64
	Tag   Tag
	Full  bool
}

func SlotFromBytes 

func SlotFromBytes(b [SlotLength]byte) Slot

func (Slot) Empty 

func (s Slot) Empty() bool

func (Slot) ToBytes 

func (s Slot) ToBytes() [SlotLength]byte

func (Slot) WithFull 

func (s Slot) WithFull(full bool) Slot

func (Slot) WithTag 

func (s Slot) WithTag(tag Tag) Slot

type SlotPointer 

type SlotPointer struct {
	Position *int64
	Slot     Slot
}

func (SlotPointer) WithSlot 

func (sp SlotPointer) WithSlot(slot Slot) SlotPointer

type SortedEntry added in v0.2.0 

type SortedEntry struct {
	KvSlot        Slot
	KeySlot       Slot
	ValuePosition int64
}

type SortedInsertResult added in v0.2.0 

type SortedInsertResult struct {
	NodePtr       int64
	Count         int64
	ValuePosition int64
	Added         bool
	Split         *SortedSplit
}

type SortedMapGetIndexPart added in v0.2.0 

type SortedMapGetIndexPart struct {
	Index int64
}

type SortedMapGetKVPair added in v0.2.0 

type SortedMapGetKVPair struct{ Key []byte }

type SortedMapGetKey added in v0.2.0 

type SortedMapGetKey struct{ Key []byte }

type SortedMapGetPart added in v0.2.0 

type SortedMapGetPart struct {
	Target SortedMapGetTarget
}

type SortedMapGetTarget added in v0.2.0 

type SortedMapGetTarget interface {
	// contains filtered or unexported methods
}

type SortedMapGetValue added in v0.2.0 

type SortedMapGetValue struct{ Key []byte }

type SortedMapInitPart added in v0.2.0 

type SortedMapInitPart struct {
	Set bool
}

type SortedMapRemovePart added in v0.2.0 

type SortedMapRemovePart struct {
	Key []byte
}

type SortedNode added in v0.2.0 

type SortedNode struct {
	Kind       BTreeNodeKind
	Num        int
	Entries    [BTreeSlotCount]Slot  // leaf
	Children   [BTreeSlotCount]Slot  // branch
	Separators [BTreeSlotCount]Slot  // branch
	Counts     [BTreeSlotCount]int64 // branch
}

func (*SortedNode) SubtreeCount added in v0.2.0 

func (n *SortedNode) SubtreeCount() int64

type SortedRemoveResult added in v0.2.0 

type SortedRemoveResult struct {
	NodePtr int64
	Found   bool
}

type SortedSlot added in v0.2.0 

type SortedSlot struct {
	Slot     Slot
	Position int64
}

type SortedSplit added in v0.2.0 

type SortedSplit struct {
	NodePtr   int64
	Count     int64
	Separator Slot
}

the new right sibling produced when a node splits

type Tag 

type Tag byte
const (
	TagNone Tag = iota
	TagIndex
	TagArrayList
	TagLinkedArrayList
	TagHashMap
	TagKVPair
	TagBytes
	TagShortBytes
	TagUint
	TagInt
	TagFloat
	TagHashSet
	TagCountedHashMap
	TagCountedHashSet
	TagSortedMap
	TagSortedSet
)

type TopLevelArrayListHeader 

type TopLevelArrayListHeader struct {
	FileSize int64
	Parent   ArrayListHeader
}

func (TopLevelArrayListHeader) ToBytes 

func (h TopLevelArrayListHeader) ToBytes() [TopLevelArrayListHeaderLength]byte

type Uint 

type Uint struct {
	Value uint64
}

func NewUint 

func NewUint(value uint64) Uint

type WriteArrayList 

type WriteArrayList struct {
	*ReadArrayList
	// contains filtered or unexported fields
}

func NewWriteArrayList 

func NewWriteArrayList(cursor *WriteCursor) (*WriteArrayList, error)

func (*WriteArrayList) All 

func (a *WriteArrayList) All() iter.Seq2[*WriteCursor, error]

func (*WriteArrayList) AllFrom added in v0.5.0 

func (a *WriteArrayList) AllFrom(index int64) iter.Seq2[*WriteCursor, error]

func (*WriteArrayList) Append 

func (a *WriteArrayList) Append(data WriteableData) error

func (*WriteArrayList) AppendContext 

func (a *WriteArrayList) AppendContext(data WriteableData, fn ContextFunction) error

func (*WriteArrayList) AppendCursor 

func (a *WriteArrayList) AppendCursor() (*WriteCursor, error)

func (*WriteArrayList) Put 

func (a *WriteArrayList) Put(index int64, data WriteableData) error

func (*WriteArrayList) PutCursor 

func (a *WriteArrayList) PutCursor(index int64) (*WriteCursor, error)

func (*WriteArrayList) Slice 

func (a *WriteArrayList) Slice(size int64) error

type WriteCountedHashMap 

type WriteCountedHashMap struct {
	*WriteHashMap
}

func NewWriteCountedHashMap 

func NewWriteCountedHashMap(cursor *WriteCursor) (*WriteCountedHashMap, error)

func (*WriteCountedHashMap) Count 

func (m *WriteCountedHashMap) Count() (int64, error)

type WriteCountedHashSet 

type WriteCountedHashSet struct {
	*WriteHashSet
}

func NewWriteCountedHashSet 

func NewWriteCountedHashSet(cursor *WriteCursor) (*WriteCountedHashSet, error)

func (*WriteCountedHashSet) Count 

func (s *WriteCountedHashSet) Count() (int64, error)

type WriteCursor 

type WriteCursor struct {
	*ReadCursor
}

func (*WriteCursor) All 

func (c *WriteCursor) All() iter.Seq2[*WriteCursor, error]

func (*WriteCursor) ReadKeyValuePair 

func (c *WriteCursor) ReadKeyValuePair() (*WriteKVPairCursor, error)

func (*WriteCursor) Write 

func (c *WriteCursor) Write(data WriteableData) error

func (*WriteCursor) WriteIfEmpty 

func (c *WriteCursor) WriteIfEmpty(data WriteableData) error

func (*WriteCursor) WritePath 

func (c *WriteCursor) WritePath(path []PathPart) (*WriteCursor, error)

func (*WriteCursor) Writer 

func (c *WriteCursor) Writer() (*CursorWriter, error)

type WriteData 

type WriteData struct {
	Data WriteableData
}

type WriteHashMap 

type WriteHashMap struct {
	*ReadHashMap
	// contains filtered or unexported fields
}

func NewWriteHashMap 

func NewWriteHashMap(cursor *WriteCursor) (*WriteHashMap, error)

func (*WriteHashMap) All 

func (m *WriteHashMap) All() iter.Seq2[*WriteCursor, error]

func (*WriteHashMap) Put 

func (m *WriteHashMap) Put(key string, data WriteableData) error

func (*WriteHashMap) PutByHash 

func (m *WriteHashMap) PutByHash(hash []byte, data WriteableData) error

func (*WriteHashMap) PutBytes 

func (m *WriteHashMap) PutBytes(key Bytes, data WriteableData) error

func (*WriteHashMap) PutCursor 

func (m *WriteHashMap) PutCursor(key string) (*WriteCursor, error)

func (*WriteHashMap) PutCursorByBytes 

func (m *WriteHashMap) PutCursorByBytes(key Bytes) (*WriteCursor, error)

func (*WriteHashMap) PutCursorByHash 

func (m *WriteHashMap) PutCursorByHash(hash []byte) (*WriteCursor, error)

func (*WriteHashMap) PutKey 

func (m *WriteHashMap) PutKey(key string, data WriteableData) error

func (*WriteHashMap) PutKeyByBytes 

func (m *WriteHashMap) PutKeyByBytes(key Bytes, data WriteableData) error

func (*WriteHashMap) PutKeyByHash 

func (m *WriteHashMap) PutKeyByHash(hash []byte, data WriteableData) error

func (*WriteHashMap) PutKeyCursor 

func (m *WriteHashMap) PutKeyCursor(key string) (*WriteCursor, error)

func (*WriteHashMap) PutKeyCursorByBytes 

func (m *WriteHashMap) PutKeyCursorByBytes(key Bytes) (*WriteCursor, error)

func (*WriteHashMap) PutKeyCursorByHash 

func (m *WriteHashMap) PutKeyCursorByHash(hash []byte) (*WriteCursor, error)

func (*WriteHashMap) Remove 

func (m *WriteHashMap) Remove(key string) (bool, error)

func (*WriteHashMap) RemoveByBytes 

func (m *WriteHashMap) RemoveByBytes(key Bytes) (bool, error)

func (*WriteHashMap) RemoveByHash 

func (m *WriteHashMap) RemoveByHash(hash []byte) (bool, error)

type WriteHashSet 

type WriteHashSet struct {
	*ReadHashSet
	// contains filtered or unexported fields
}

func NewWriteHashSet 

func NewWriteHashSet(cursor *WriteCursor) (*WriteHashSet, error)

func (*WriteHashSet) All 

func (s *WriteHashSet) All() iter.Seq2[*WriteCursor, error]

func (*WriteHashSet) Put 

func (s *WriteHashSet) Put(key string) error

func (*WriteHashSet) PutByHash 

func (s *WriteHashSet) PutByHash(hash []byte, data WriteableData) error

func (*WriteHashSet) PutBytes 

func (s *WriteHashSet) PutBytes(key Bytes) error

func (*WriteHashSet) PutCursor 

func (s *WriteHashSet) PutCursor(key string) (*WriteCursor, error)

func (*WriteHashSet) PutCursorByBytes 

func (s *WriteHashSet) PutCursorByBytes(key Bytes) (*WriteCursor, error)

func (*WriteHashSet) PutCursorByHash 

func (s *WriteHashSet) PutCursorByHash(hash []byte) (*WriteCursor, error)

func (*WriteHashSet) Remove 

func (s *WriteHashSet) Remove(key string) (bool, error)

func (*WriteHashSet) RemoveByBytes 

func (s *WriteHashSet) RemoveByBytes(key Bytes) (bool, error)

func (*WriteHashSet) RemoveByHash 

func (s *WriteHashSet) RemoveByHash(hash []byte) (bool, error)

type WriteKVPairCursor 

type WriteKVPairCursor struct {
	ValueCursor *WriteCursor
	KeyCursor   *WriteCursor
	Hash        []byte
}

type WriteLinkedArrayList 

type WriteLinkedArrayList struct {
	*ReadLinkedArrayList
	// contains filtered or unexported fields
}

func NewWriteLinkedArrayList 

func NewWriteLinkedArrayList(cursor *WriteCursor) (*WriteLinkedArrayList, error)

func (*WriteLinkedArrayList) All 

func (a *WriteLinkedArrayList) All() iter.Seq2[*WriteCursor, error]

func (*WriteLinkedArrayList) AllFrom added in v0.5.0 

func (a *WriteLinkedArrayList) AllFrom(index int64) iter.Seq2[*WriteCursor, error]

func (*WriteLinkedArrayList) Append 

func (a *WriteLinkedArrayList) Append(data WriteableData) error

func (*WriteLinkedArrayList) AppendCursor 

func (a *WriteLinkedArrayList) AppendCursor() (*WriteCursor, error)

func (*WriteLinkedArrayList) Concat 

func (a *WriteLinkedArrayList) Concat(list Slot) error

func (*WriteLinkedArrayList) Insert 

func (a *WriteLinkedArrayList) Insert(index int64, data WriteableData) error

func (*WriteLinkedArrayList) InsertCursor 

func (a *WriteLinkedArrayList) InsertCursor(index int64) (*WriteCursor, error)

func (*WriteLinkedArrayList) Put 

func (a *WriteLinkedArrayList) Put(index int64, data WriteableData) error

func (*WriteLinkedArrayList) PutCursor 

func (a *WriteLinkedArrayList) PutCursor(index int64) (*WriteCursor, error)

func (*WriteLinkedArrayList) Remove 

func (a *WriteLinkedArrayList) Remove(index int64) error

func (*WriteLinkedArrayList) Slice 

func (a *WriteLinkedArrayList) Slice(offset, size int64) error

type WriteMode 

type WriteMode int
const (
	ReadOnly WriteMode = iota
	ReadWrite
)

type WriteSortedMap added in v0.2.0 

type WriteSortedMap struct {
	*ReadSortedMap
	// contains filtered or unexported fields
}

func NewWriteSortedMap added in v0.2.0 

func NewWriteSortedMap(cursor *WriteCursor) (*WriteSortedMap, error)

func (*WriteSortedMap) All added in v0.2.0 

func (m *WriteSortedMap) All() iter.Seq2[*WriteCursor, error]

func (*WriteSortedMap) AllFrom added in v0.5.0 

func (m *WriteSortedMap) AllFrom(startKey []byte) iter.Seq2[*WriteCursor, error]

func (*WriteSortedMap) AllFromIndex added in v0.5.0 

func (m *WriteSortedMap) AllFromIndex(startIndex int64) iter.Seq2[*WriteCursor, error]

func (*WriteSortedMap) Put added in v0.2.0 

func (m *WriteSortedMap) Put(key string, data WriteableData) error

func (*WriteSortedMap) PutByBytes added in v0.2.0 

func (m *WriteSortedMap) PutByBytes(key []byte, data WriteableData) error

func (*WriteSortedMap) PutCursor added in v0.2.0 

func (m *WriteSortedMap) PutCursor(key string) (*WriteCursor, error)

func (*WriteSortedMap) PutCursorByBytes added in v0.2.0 

func (m *WriteSortedMap) PutCursorByBytes(key []byte) (*WriteCursor, error)

func (*WriteSortedMap) Remove added in v0.2.0 

func (m *WriteSortedMap) Remove(key string) (bool, error)

func (*WriteSortedMap) RemoveByBytes added in v0.2.0 

func (m *WriteSortedMap) RemoveByBytes(key []byte) (bool, error)

type WriteSortedSet added in v0.2.0 

type WriteSortedSet struct {
	*ReadSortedSet
	// contains filtered or unexported fields
}

func NewWriteSortedSet added in v0.2.0 

func NewWriteSortedSet(cursor *WriteCursor) (*WriteSortedSet, error)

func (*WriteSortedSet) All added in v0.2.0 

func (s *WriteSortedSet) All() iter.Seq2[*WriteCursor, error]

func (*WriteSortedSet) AllFrom added in v0.5.0 

func (s *WriteSortedSet) AllFrom(startKey []byte) iter.Seq2[*WriteCursor, error]

func (*WriteSortedSet) AllFromIndex added in v0.5.0 

func (s *WriteSortedSet) AllFromIndex(startIndex int64) iter.Seq2[*WriteCursor, error]

func (*WriteSortedSet) Put added in v0.2.0 

func (s *WriteSortedSet) Put(key string) error

func (*WriteSortedSet) PutByBytes added in v0.2.0 

func (s *WriteSortedSet) PutByBytes(key []byte) error

func (*WriteSortedSet) Remove added in v0.2.0 

func (s *WriteSortedSet) Remove(key string) (bool, error)

func (*WriteSortedSet) RemoveByBytes added in v0.2.0 

func (s *WriteSortedSet) RemoveByBytes(key []byte) (bool, error)

type WriteableData 

type WriteableData interface {
	// contains filtered or unexported methods
}

Source Files

View all Source files

Directories

Path Synopsis
cmd
dump-database command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.