Save the Trees
Published: 2019-09-10 05:05:50

Part 8, with [part 7 back here](https://dev.to/quoll/shaking-the-tree-2oi2), or go back to [the beginning](https://dev.to/quoll/what-s-with-data-structures-2fk7).

# Revisiting Mapped Files
Now that we've seen the structural differences in tree nodes vs. linked list elements, we have what we need to update the [BufferList](https://dev.to/quoll/mapping-the-way-3fn#buffer-list) class to handle trees instead of lists.

The first thing to consider is the layout of each tree node on disk:
```java
public static int NODE_SIZE = 3 * Integer.BYTES;
private static int VALUE_OFFSET = 0;
private static int LEFT_OFFSET = 1;
private static int RIGHT_OFFSET = 2;
```
Note how the size of the node is in bytes, but the offsets are all given as integer offsets. If not for the `IntBuffer` view of the data, all the offsets would be in bytes, and our code would have to use these offsets, and then read the appropriate number of bytes before gluing them together into an `Integer` value. Fortunately, the `IntBuffer` class already does all of that for us.

With the linked list file we needed to store some metadata for the file, and put that in a separate file. This time we can do something a little different. The metadata that we want to store is the offset of the next node that can be allocated, and the offset of the node that forms the root of the tree. This is just 2 integers, which makes it possible to fit inside the space typically allocated for a `Node`. If we reserve the location of the first `Node` at offset 0 then we can use it to store this metadata instead. In this case, it means that we will not need a second file, which is convenient, though for more complex structures we will probably still want that metafile.

Using `0` as an invalid address mirrors the way the CPUs and Operating Systems usually work. The `0` address represents an invalid part of memory, meaning that every reference to it indicates invalid or uninitialized memory. Typically all of the first few physical addresses indicate an error, though the CPU will use them for its own purposes, such as holding addresses for code to run in the event of a Hardware Interrupt on older systems. So storing our metadata at the `0` offset has an analogy that I like.

A second benefit to this approach is that the `NULL` reference will now be `0` instead of `-1`. This is useful because Java ensures that all fresh buffers are initialized to the `0`, which means that when a new `Node` is allocated, the children will already be set to `NULL`. (C and C++ do not do this unless you use `calloc` to allocate memory).

<a name="layout"/>Now that we know that the first `Node` space will hold metadata, we have an expanded set of constants to work with:
```java
public static int NODE_SIZE = 3 * Integer.BYTES;
public static int META_SIZE = 2 * Integer.BYTES;
public static int NULL = 0;

// META offsets
private static int NEXT_AVAILABLE_OFFSET = 0;
private static int ROOT_OFFSET = 1;

// Node offsets
private static int VALUE_OFFSET = 0;
private static int LEFT_OFFSET = 1;
private static int RIGHT_OFFSET = 2;
```

##Constructing
With the constants in place, the data necessary for the tree can be declared. That includes the file, along with the channel so that it can be mapped into a buffer. We want the `ByteBuffer` representing all the data in the file, as this is the basis for overlaying `Node`s onto the file. Finally, we want a buffer reference to access the metadata and a Node that represents the root of the tree.
```java
private final RandomAccessFile file;                                                                                    
private final FileChannel fileChannel;
private ByteBuffer buffer;
private IntBuffer metaBuffer;
private Node root;
```

The constructor will do a similar job to what it did for the `BufferList` class. The file is opened, and if it is not long enough, it gets expanded, or if it's too long it gets truncated.
```java
long fileLength = NODE_SIZE * length;
File ioFile = new File(filename);
boolean exists = ioFile.exists();
file = new RandomAccessFile(filename, "rw");
if (exists && file.length() > fileLength) {
  fileLength = file.length();
} else if (fileLength > file.length()) {
  file.setLength(fileLength);
}
```
<a name="meta"/>Once the file is the expected size, it can be mapped. Those first few bytes of the mapped buffer are then captured as a buffer for the metadata.
```java
fileChannel = file.getChannel();
buffer = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, fileLength);
metaBuffer = buffer.limit(META_SIZE).position(0).slice().asIntBuffer();
```
Finally, some data initialization can happen. If the file did not exist before, then the first position available to put a node in the offset for `Node 1`. Otherwise, that position will be read from the metadata. Also, the root of the tree will be `null` if the file is new, or else once the offset has been read from the metadata the root node can be constructed:
```java
if (!exists) {
  setNextAvailable(1);
}
int rootIndex = metaBuffer.get(ROOT_OFFSET);
root = rootIndex == NULL ? null : new Node(rootIndex);
```
The `setNextAvailable` method is just updating the metadata
```java
private void setNextAvailable(int next) {
  metaBuffer.put(NEXT_AVAILABLE_OFFSET, next);
}
```
Calling `close()` on the tree will just close of these files, as with the `BufferList`. We needn't include it here, but it will be in the final file that I'll link at the end.

##Growing a Tree
Adding to the tree follows a very similar structure to the [Javascript in the previous post](https://dev.to/quoll/shaking-the-tree-2oi2#tree).
```java
public Node add(int value) {
  Node node = new Node(getAndIncNextAvailable(), value);
  if (root == null) {
    setRoot(node);
  } else {
    insertNode(root, node);
  }
  return root;
}
```
The main different here is the `Node` constructor which is taking the node ID for the next free node. Note that this is retrieved with a function that gets the ID and increments it:<a name="getAndIncNextAvailable"/>
```java
private int getAndIncNextAvailable() {
  int next = metaBuffer.get(NEXT_AVAILABLE_OFFSET);
  if ((next + 1) * NODE_SIZE > buffer.capacity()) {
    throw new RuntimeException("Out of capacity");
  }
  metaBuffer.put(NEXT_AVAILABLE_OFFSET, next + 1);
  return next;
}
```
This just reads the _next available_ value from metadata, increments the stored value, and returns the read value.

As with the `BufferList` class, if the entire buffer is full, then an exception will be thrown. In production, we would want to deal with this situation by expanding the file, but that's beyond what we're looking at for now. While considering production code, it is also worth considering that more than one thread could be calling this code at once. If this is the case, then this function should be protected with a `synchronized` keyword, to avoid a possible race condition for the _next available_ value.

The `insertNode` method will be very similar to the [`insertNode` method in for the Javascript tree](https://dev.to/quoll/shaking-the-tree-2oi2#insert-node).
```java
private void insertNode(Node node, Node newNode) {
  int value = node.getValue();
  if (newNode.getValue() < value) {
    Node left = node.getLeft();
    if (left == null) {
      node.setLeft(newNode);
    } else {
      insertNode(left, newNode);
    }
  } else {
    Node right = node.getRight();
    if (right == null) {
      node.setRight(newNode);
    } else {
      insertNode(right, newNode);
    }
  }
}
```
The only differences from the original Javascript are that the `this` identifier is optional for methods on the current object, and because the _left_ and _right_ values are accessed with _getter_ methods then we are only calling the method once and holding onto the returned value.

Getter methods are required in general with these objects, as they are wrapping operations that retrieve objects from the buffer, while the Javascript code is able to just follow memory references. We see this also in the methods for accessing the root of the tree, although because this is metadata that gets read on initialization, the getter does not need to touch the buffer:
```java
private void setRoot(Node node) {
  root = node;
  metaBuffer.put(ROOT_OFFSET, node.getIndex());
}

public Node getRoot() {
  return root;
}
```
###Printing
As before, printing is a recursive process that first prints the left branch, then prints the node value, and finally prints the right branch, with various `if` or ternary statements in place to make sure an appropriate number of commas are added:
```java
public String toString() {
  return root.toString();
}

public static String treeString(Node element) {
  Node left = element.getLeft();
  Node right = element.getRight();
  return (left == null ? "" : treeString(left)) +
         Integer.toString(element.getValue()) +
         (right == null ? "" : treeString(right));
}
```

##Nodes
As with the `BufferList` elements, nodes overlay a buffer. The first step to creating a node is to slice out that part of the buffer that the node is wrapping, and represents it as Integer values. If the node is initialized with just a buffer reference, it can be used to read what was already there, and if it is initialized with a value, it will write that value to the buffer.
```java
private final IntBuffer intBuffer;
private final int index;

Node(int index) {
  this.index = index;
  int offset = index * NODE_SIZE;
  if (offset > buffer.limit()) {
    intBuffer = buffer.limit(offset + NODE_SIZE).position(offset).slice().asIntBuffer();
  } else {
    intBuffer = buffer.position(offset).limit(offset + NODE_SIZE).slice().asIntBuffer();
  }
}

Node(int index, int value) {
  this(index);
  setValue(value);
  setLeft(null);
  setRight(null);
}
```
<a name="gettersAndSetters"/>The `index` is read-only, but the other values are all accessible via _getters_ and _setters_, which all wrap buffer operations:
```java
public int getValue() {
  return intBuffer.get(VALUE_OFFSET);
}

public Node getLeft() {
  int leftId = intBuffer.get(LEFT_OFFSET);
  return leftId == NULL ? null : new Node(leftId);
}

public Node getRight() {
  int rightId = intBuffer.get(RIGHT_OFFSET);
  return rightId == NULL ? null : new Node(rightId);
}

public Node setValue(int value) {
  intBuffer.put(VALUE_OFFSET, value);
  return this;
}

public Node setLeft(Node left) {
  intBuffer.put(LEFT_OFFSET, left == null ? NULL : left.getIndex());
  return this;
}

public Node setRight(Node right) {
  intBuffer.put(RIGHT_OFFSET, right == null ? NULL : right.getIndex());
  return this;
}
```
The complete code for [`BufferTree` is here](https://gist.github.com/quoll/ec455ae7a66cf4d683768b41dc805628).

##Using the Tree
<a name="use"/>Creating this tree and adding the digits of π is straightforward:
```java
BufferTree bufferTree = new BufferTree("tree.bin", 25);
bufferTree.add(3);
bufferTree.add(1);
bufferTree.add(4);
bufferTree.add(1);
bufferTree.add(5);
bufferTree.add(9);
bufferTree.add(2);
bufferTree.add(6);
bufferTree.add(5);
bufferTree.add(3);
```
Alternatively, the `add` operations could be chained:
`bufferTree.add(3).add(1).add(4).add(1).add(5).add(9).add(2).add(6).add(5).add(3);`
But I didn't do it that way, because most use cases for populating a tree are when the data comes from external source, and not hard coded like this.

Printing the tree shows that all the data has been sorted:
```java
System.out.println(bufferTree);
```
```bash
$ java tree.TreeExample
1, 1, 2, 3, 3, 4, 5, 5, 6, 9
```
What happens if the same program is run again, loading the data a second time?
```bash
$ java tree.TreeExample
1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 9, 9
```

That's all of the original data repeated and in order.

How about reading the data back? That's exactly the same, without the loading step:
```java
public class TreeExample2 {
  public static void main(String[] args) throws IOException {
    BufferTree bufferTree = new BufferTree("tree.bin", 25);
    System.out.println(bufferTree);
    bufferTree.close();
  }
}
```
Resulting in:
```bash
$ java tree.TreeExample2
1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 9, 9
```

These example programs are also found at the bottom of the [gist for the `BufferTree`](https://gist.github.com/quoll/ec455ae7a66cf4d683768b41dc805628).

##Regrowth
This post was just a reiteration of the tree structure described in the previous post, combined with the buffer wrapping approach described in [Part 6](https://dev.to/quoll/mapping-the-way-3fn). This creates a binary tree on disk that can be re-read with ease.

We are now referring to the `0` offset in the buffer as an invalid address, which allows us to use the initial values in the buffer (which are always `0`) to indicate null entries. This also allowed us to shift some of the metadata for the tree into the head of the file, though this will have limited utility as metadata requirements expand in later posts.

Given that most databases use some variant of [B-Tree](https://en.wikipedia.org/wiki/B-tree), this discussion of binary trees may seem like an unusual focus, but it will all become clear eventually. (I promise!)

But before then, we should look at [how to balance these trees](https://dev.to/quoll/a-balanced-tree-27ik).