内置库来持久保存BTree，相当于Java的FileChannel和ByteBuffer

Question

So, I wrote this persistent BTree in Java, following the CLRS algorithms. I used FileChannel and ByteBuffer to store the tree in a file, reading and writing the nodes when needed.

I tried looking how I could store such a BTree in Go, and discovered os.File, which I think could be used the same way as Java's FileChannel. However, I could not find an equivalent for ByteBuffer. I looked at bytes.Buffer, and I see how this could work, however it does not have the ByteBuffer's handy putInt, putDouble, etc...

Would I have to implement myself those function to transform ints and doubles to byte arrays? I also looked at encoding.binary, but this looks very cumbersome. I understand that I would have to encode my variables to a byte array every time, then copy that byte array to the buffer.

What structures would be recommended in this case?

Answer 1

Using the encoding/gob package

Using the encoding/gob package you can serialize entire trees into a series of bytes and deserialize them with a single method call.

See this example:

type Node struct {
    Data     int
    Children []*Node
}

func (n *Node) String() string {
    buf := &bytes.Buffer{}
    buf.WriteString(fmt.Sprintf("Node[Data: %d, Children: [", n.Data))
    for i, v := range n.Children {
        if i > 0 {
            buf.WriteString(", ")
        }
        buf.WriteString(v.String())
    }
    buf.WriteString("]")
    return buf.String()
}

The Node.String() method is not required, I only created it to easily print / verify the tree.

Now using gob to serialize and deserialize a tree:

root := &Node{
    Data: 1,
    Children: []*Node{
        {Data: 2},
        {Data: 3},
    },
}
fmt.Println(root)

buf := &bytes.Buffer{}
if err := gob.NewEncoder(buf).Encode(root); err != nil {
    panic(err)
}

var root2 *Node
if err := gob.NewDecoder(buf).Decode(&root2); err != nil {
    panic(err)
}
fmt.Println(root2)

Output (try it on the Go Playground):

Node[Data: 1, Children: [Node[Data: 2, Children: [], Node[Data: 3, Children: []]
Node[Data: 1, Children: [Node[Data: 2, Children: [], Node[Data: 3, Children: []]

Here I used an in-memory buffer (bytes.Buffer), but if you want to save to / load from a file, you don't even need an in-memory buffer, you can directly pass an *os.File value to gob.NewEncoder() and gob.NewDecoder() (as *os.File implements both io.Reader and io.Writer).

Manual serialization / deserialization

Also note that if you don't want to (or can't) use encoding/gob to do the complete serialization in one step, you can also use binary.Write() and binary.Read() functions to directly write to / read from your file without using any in-memory buffers.

See this example encoding and decoding an int32 and a float64 value:

var i int32
var f float64

i, f = 1, 3.14

buf := &bytes.Buffer{}
if err := binary.Write(buf, binary.LittleEndian, i); err != nil {
    panic(err)
}
if err := binary.Write(buf, binary.LittleEndian, f); err != nil {
    panic(err)
}

var i2 int32
var f2 float64
if err := binary.Read(buf, binary.LittleEndian, &i2); err != nil {
    panic(err)
}
if err := binary.Read(buf, binary.LittleEndian, &f2); err != nil {
    panic(err)
}

fmt.Println(i2, f2)

Output (try it on the Go Playground):

1 3.14

Again, you can pass your file directly to binary.Read() and binary.Write() instead of *bytes.Buffer.

Non-binary serialization

You could also use other, non-binary serialization formats such as JSON. The encoding/json package will also be able to serialize / deserialize your entire tree with a single call. Using JSON would be less performant in terms of storage and speed though, but the serialized format would be more human-friendly (more readable / editable), and compatible with other applications / technologies.