A pointer costs 8 bytes to store on a modern 64-bit system, but unless your planning on storing over 4 billion nodes in memory, an index can be stored in just 4 bytes.

Due to the reduced node size and the fact that nodes are stored contiguously in memory, the data structure will fit into fewer memory pages and more nodes will fit in the cpu’s cache line, which generally improves access times significantly.

The way most people learn to implement data structures like trees is to make a separate allocation for each individual node, one at a time. This is a very naive way of allocating memory, however, as each memory allocation comes with a small but significant overhead which can really slow things down for a large number of nodes. Storing nodes in a growable arraylist minimizes this overhead as arraylists grow superlinearly (e.g, doubling in size each time more space is needed) meaning the majority of new nodes can just be placed in the next available slot without requesting more memory!

Freeing structures which are allocated in the traditional “nest of pointers” fashion can be very slow, as the entire structure has to be traversed to find and individually free each node. Storing nodes in a single allocation eliminates this problem entirely and freeing the structure becomes just a single free call, as it should be.

One disadvantage of storing all the nodes in a contiguous buffer is that it makes it harder to free an individual node as removing a single element from an arraylist would involve shifting over all the elements after it, a linear time operation which is almost always too slow to be practical. In practice this isn’t something you normally need to do as many data structures, like an AST, can be freed all at once, but if you need to be able to free individual nodes and still want to use this technique then the obvious solution would be to use a freelist.

Freelists

A freelist is, as the name suggests, a list used to track free slots in memory allocators. In our case we can simply use a stack to store indices of free slots in our arraylist and attempt to pop off this stack any time we add a new element. The extra code complexity should be weighed against the actual performance benefit when considering this approach.

Here is a short demo of this technique in Zig (v0.14.1). There are some Zig quirks involved like passing memory allocators and using an enum as an index type but hopefully the general idea is clear.

pub fn main() !void {
    var debug_allocator = std.heap.DebugAllocator(.{}).init;
    defer _ = debug_allocator.deinit();

    var tree = Tree{
        
        .nodes = ArrayList(Tree.Node).init(debug_allocator.allocator()),
    };
    defer tree.nodes.deinit();

    
    const root = try tree.createNode(45);

    const a = try tree.createNode(-10);
    const b = try tree.createNode(89000);
    const c = try tree.createNode(2);

    tree.setLeftChild(root, a);
    tree.setRightChild(root, b);
    tree.setLeftChild(b, c);

    printTree(&tree);
}

const Tree = struct {
    
    nodes: ArrayList(Node),

    const Node = struct {
        data: i32,
        left_child: NodeIndex = .none,
        right_child: NodeIndex = .none,
    };

    
    
    const NodeIndex = enum(u32) {
        
        none = 0,
        _,
    };

    fn createNode(tree: *Tree, value: i32) std.mem.Allocator.Error!NodeIndex {
        const index: NodeIndex = @enumFromInt(@as(u32, @intCast(tree.nodes.items.len)));
        try tree.nodes.append(.{ .data = value });
        return index;
    }

    fn setLeftChild(tree: *const Tree, parent: NodeIndex, child: NodeIndex) void {
        tree.nodes.items[@intFromEnum(parent)].left_child = child;
    }

    fn setRightChild(tree: *const Tree, parent: NodeIndex, child: NodeIndex) void {
        tree.nodes.items[@intFromEnum(parent)].right_child = child;
    }
};

fn printTree(tree: *const Tree) void {
    assert(tree.nodes.items.len > 0);

    
    printNode(tree, @enumFromInt(0), 0);
}

fn printNode(tree: *const Tree, node_index: Tree.NodeIndex, depth: u32) void {
    const node = tree.nodes.items[@intFromEnum(node_index)];

    for (0..depth) |_| print("  ", .{});
    print("[{d}] {d}\n", .{ @intFromEnum(node_index), node.data });

    if (node.left_child != .none) printNode(tree, node.left_child, depth + 1);
    if (node.right_child != .none) printNode(tree, node.right_child, depth + 1);
}

const std = @import("std");
const ArrayList = std.ArrayList;
const assert = std.debug.assert;
const print = std.debug.print;

And here is the output:

$ zig run indices.zig
[0] 45
  [1] -10
  [2] 89000
    [3] 2