Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index

scipio

Published: 01 Aug 2026 › Updated: 01 Aug 2026 Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index

Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index

What will I learn?

Why the obvious way to search -- scan every document for the word on every query -- is fine for a shoebox of files and hopeless the moment the pile grows, and how to measure exactly why;
The one structure that turns search from "read everything" into "read almost nothing": the inverted index, which maps each word back to the list of documents that contain it;
Building a real tokenizer in Zig -- lowercasing, splitting on punctuation, yielding terms -- and the subtle ownership question of who holds the term strings once they land in a hash map;
Storing postings lists (a sorted run of document ids plus a term-frequency count) and why keeping them sorted is the single decision that makes everything downstream fast;
Answering boolean AND queries by intersecting sorted postings in linear time with a two-pointer merge, rarest term first, so "systems language" finds only the docs holding both words;
Where the same machinery shows up in C, Rust and Go, and why every search box you have ever typed into runs on this idea;
But first, the debt: last episode's three consistent-hashing exercises (weighted nodes, replica placement, and honestly measuring load imbalance), in full compilable code ;-)

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
Episode 124 (Consistent Hashing) still warm -- we pay off its three exercises at the top, and the ring reappears in the first solution;
The hash-map comfort from episode 22, the sorted-array binary search from episode 117, and the std.ArrayList reflexes we have been drilling all through the data-structures run;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index

At the end of last episode I made you a promise. We had just built a hash ring that spreads keys across a fleet of servers without the whole cluster melting every time it resizes -- and I said that once you have filled a toolbox this deep (hash maps, tries, B-trees, filters, sorting, searching, an LRU cache, a distribution ring) the only honest thing left to do is build something real with it. So that is what the next few episodes are: a small search engine, assembled from scratch, piece by piece. Today we lay the foundation stone -- the data structure that answers the one question every search box on earth has to answer in milliseconds: which documents contain the word you just typed?

But we owe a debt first. Episode 124 left you three exercises on the consistent-hashing ring, and I promised full code, not hand-waving. Let us clear the ledger ;-)

Solutions to Episode 124 Exercises

Exercise 1 -- weighted nodes. Real clusters are lopsided: a beefy 128GB box should hold more keys than a tiny 16GB one. The task was to let addNode take a weight and place vnodes * weight virtual points for that server in stead of a flat vnodes. That is a genuinely small change -- the ring already places many points per node, so weighting is just "place proportionally more". Here is the ring from last episode with the weighted addNode, plus the two methods the other exercises need (we build on this same struct for all three):

const std = @import("std");

const HashRing = struct {
    const Point = struct { hash: u64, node: []const u8 };

    gpa: std.mem.Allocator,
    ring: std.ArrayList(Point), // kept sorted by hash
    vnodes: u32,

    fn init(gpa: std.mem.Allocator, vnodes: u32) HashRing {
        std.debug.assert(vnodes >= 1);
        return .{ .gpa = gpa, .ring = .empty, .vnodes = vnodes };
    }
    fn deinit(self: *HashRing) void {
        self.ring.deinit(self.gpa);
    }
    fn lessThan(_: void, a: Point, b: Point) bool {
        return a.hash < b.hash;
    }
    fn pointHash(name: []const u8, replica: u32) u64 {
        var buf: [128]u8 = undefined;
        const label = std.fmt.bufPrint(&buf, "{s}#{d}", .{ name, replica }) catch unreachable;
        return std.hash.Wyhash.hash(0, label);
    }
    // weight scales how many virtual points a node contributes to the ring
    fn addNode(self: *HashRing, name: []const u8, weight: u32) !void {
        std.debug.assert(weight >= 1);
        const total = self.vnodes * weight;
        var r: u32 = 0;
        while (r < total) : (r += 1) {
            try self.ring.append(self.gpa, .{ .hash = pointHash(name, r), .node = name });
        }
        std.mem.sort(Point, self.ring.items, {}, lessThan);
    }
    fn locate(self: *const HashRing, target: u64) usize {
        var lo: usize = 0;
        var hi: usize = self.ring.items.len;
        while (lo < hi) {
            const mid = lo + (hi - lo) / 2;
            if (self.ring.items[mid].hash < target) lo = mid + 1 else hi = mid;
        }
        if (lo == self.ring.items.len) lo = 0; // ran off the top -> wrap to index 0
        return lo;
    }
    fn nodeFor(self: *const HashRing, key: []const u8) []const u8 {
        std.debug.assert(self.ring.items.len > 0);
        return self.ring.items[self.locate(std.hash.Wyhash.hash(0, key))].node;
    }
};

test "a doubly weighted node gets roughly double the key share" {
    const gpa = std.testing.allocator;
    var ring = HashRing.init(gpa, 200);
    defer ring.deinit();
    try ring.addNode("heavy", 2);
    try ring.addNode("light-a", 1);
    try ring.addNode("light-b", 1);

    var counts = std.StringHashMap(usize).init(gpa);
    defer counts.deinit();
    for (0..40_000) |i| {
        var kb: [24]u8 = undefined;
        const key = std.fmt.bufPrint(&kb, "k{d}", .{i}) catch unreachable;
        const gop = try counts.getOrPut(ring.nodeFor(key));
        if (!gop.found_existing) gop.value_ptr.* = 0;
        gop.value_ptr.* += 1;
    }
    const heavy = counts.get("heavy").?;
    const light = counts.get("light-a").?;
    const r = @as(f64, @floatFromInt(heavy)) / @as(f64, @floatFromInt(light));
    try std.testing.expect(r > 1.6 and r < 2.4); // ~2x, within statistical slop
}

The whole exercise is the single line const total = self.vnodes * weight;. Because the load a node carries is proportional to the fraction of ring arc its points cover, and its point count is now proportional to its weight, the load comes out proportional to the weight -- exactly the knob you wanted. The test asserts "roughly two", not "exactly two", because random hashing never gives you a perfect ratio; demanding equality would be a flaky test that lies about the maths.

Exercise 2 -- bounded replica lookup, no scan. Every replicated store needs to know not just the owner of a key, but the first count distinct servers clockwise from it, so it can place the N copies of a value on N different machines. The trap is virtual nodes: as you walk the ring you keep bumping into more points that belong to a server you already collected, and you must skip them. Here is nodesFor, which drops straight into the HashRing above:

// first `count` DISTINCT physical nodes clockwise from a key -> written into out
fn nodesFor(self: *const HashRing, key: []const u8, count: usize, out: [][]const u8) usize {
    if (self.ring.items.len == 0 or count == 0) return 0;
    var idx = self.locate(std.hash.Wyhash.hash(0, key));
    var found: usize = 0;
    var steps: usize = 0;
    while (found < count and steps < self.ring.items.len) : (steps += 1) {
        const candidate = self.ring.items[idx].node;
        var seen = false;
        for (out[0..found]) |already| {
            if (std.mem.eql(u8, already, candidate)) {
                seen = true;
                break;
            }
        }
        if (!seen) {
            out[found] = candidate;
            found += 1;
        }
        idx += 1;
        if (idx == self.ring.items.len) idx = 0; // wrap
    }
    return found;
}

test "nodesFor returns distinct servers for replica placement" {
    const gpa = std.testing.allocator;
    var ring = HashRing.init(gpa, 200);
    defer ring.deinit();
    for ([_][]const u8{ "s0", "s1", "s2", "s3" }) |name| try ring.addNode(name, 1);

    var out: [3][]const u8 = undefined;
    for (0..1000) |i| {
        var kb: [24]u8 = undefined;
        const key = std.fmt.bufPrint(&kb, "obj-{d}", .{i}) catch unreachable;
        try std.testing.expectEqual(@as(usize, 3), ring.nodesFor(key, 3, &out));
        try std.testing.expect(!std.mem.eql(u8, out[0], out[1]));
        try std.testing.expect(!std.mem.eql(u8, out[0], out[2]));
        try std.testing.expect(!std.mem.eql(u8, out[1], out[2]));
    }
}

The steps < self.ring.items.len guard is the safety belt: it stops us looping forever if the caller asks for more distinct servers than physically exist. The linear scan of out[0..found] to check for duplicates looks wasteful, but count is tiny in practice (three, maybe five replicas), so it is cheaper than any set. Notice the caller supplies the out buffer -- no allocation inside a hot lookup, a pattern we have leaned on all series.

Exercise 3 -- measure the imbalance honestly. The point of virtual nodes is even load, and the point of this exercise is to see the diminishing return with your own eyes. The helper below tallies how many keys land on each node and returns the ratio of the busiest node's load to the mean:

fn loadRatio(ring: *const HashRing, gpa: std.mem.Allocator, key_count: usize) !f64 {
    var tally = std.StringHashMap(usize).init(gpa);
    defer tally.deinit();
    for (0..key_count) |i| {
        var kb: [24]u8 = undefined;
        const key = std.fmt.bufPrint(&kb, "user:{d}", .{i}) catch unreachable;
        const gop = try tally.getOrPut(ring.nodeFor(key));
        if (!gop.found_existing) gop.value_ptr.* = 0;
        gop.value_ptr.* += 1;
    }
    var max: usize = 0;
    var it = tally.valueIterator();
    while (it.next()) |v| max = @max(max, v.*);
    const mean = @as(f64, @floatFromInt(key_count)) / @as(f64, @floatFromInt(tally.count()));
    return @as(f64, @floatFromInt(max)) / mean;
}

test "load ratio flattens out as virtual nodes climb" {
    const gpa = std.testing.allocator;
    for ([_]u32{ 1, 10, 50, 200 }) |vn| {
        var ring = HashRing.init(gpa, vn);
        defer ring.deinit();
        for ([_][]const u8{ "a", "b", "c", "d", "e" }) |name| try ring.addNode(name, 1);
        const ratio = try loadRatio(&ring, gpa, 20_000);
        try std.testing.expect(ratio >= 1.0);
        if (vn >= 200) try std.testing.expect(ratio < 1.2); // near-flat by 200
    }
}

Print that ratio for vnodes of 1, 10, 50, 200 and 500 and the shape of the curve tells the whole story: going from 1 to 50 is night and day, but 200 to 500 barely moves the needle. That plateau is exactly why production systems park their replica count in the low hundreds and stop -- more virtual nodes past that point buy you fractions of a percent of fairness for a linear cost in ring size. Debt paid ;-) Now, the search engine.

The naive way, and why it collapses

Let us be honest about the starting point, because you have to feel the pain before the fix means anything. You have a pile of documents and a word to find. The first thing anyone writes -- and it is not wrong, exactly, just doomed -- is to walk every document and check whether the word appears in it:

const std = @import("std");

const Doc = struct { id: u32, text: []const u8 };

fn linearSearch(gpa: std.mem.Allocator, corpus: []const Doc, needle: []const u8) !std.ArrayList(u32) {
    var hits: std.ArrayList(u32) = .empty;
    for (corpus) |doc| {
        if (std.mem.indexOf(u8, doc.text, needle) != null) {
            try hits.append(gpa, doc.id);
        }
    }
    return hits;
}

test "linear scan finds the right docs but reads every byte" {
    const gpa = std.testing.allocator;
    const corpus = [_]Doc{
        .{ .id = 0, .text = "the quick brown fox" },
        .{ .id = 1, .text = "the lazy dog sleeps" },
        .{ .id = 2, .text = "a quick red fox" },
    };
    var hits = try linearSearch(gpa, &corpus, "quick");
    defer hits.deinit(gpa);
    try std.testing.expectEqualSlices(u32, &.{ 0, 2 }, hits.items);
}

It works. It returns the right answer. And it is a disaster at scale, for a reason that is worth stating precisely: the cost of a query is proportional to the total size of the entire corpus. Every single query reads every single byte you have ever indexed. Ten thousand documents averaging two kilobytes each is twenty megabytes scanned for the word "the", and then another twenty megabytes scanned for the next query, and the next. Double the corpus and you double every query. This is the "obvious but ruinously slow" pattern we keep running into -- quick-find in the union-find episode, modulo hashing last time -- and the fix is always the same move: do the expensive work once, up front, and store the result in a shape that makes the question cheap. A part from that, std.mem.indexOf matches substrings, so searching for "cat" would happily match "category" -- rarely what a search box wants. We need to think in words, not bytes.

Flipping the problem inside-out

Here is the idea, and it is one of those that feels inevitable the moment you see it. The naive index is a mapping from document to its words -- a forward index. To answer "which documents contain X" you are forced to check every document, because the mapping runs the wrong way. So we flip it. We build the mapping from word to the documents that contain it. That is the inverted index, and the list of documents attached to a single word is its postings list.

With the mapping running that direction, a query stops being a search and becomes a lookup. "Which documents contain quick?" is now: hash the word "quick", pull its postings list straight out of a hash map, done -- in time proportional to the length of that one list, not the size of the whole corpus. The word "elephant", absent from every document, is an instant miss. The heavy lifting all happens once, at index time, when we read each document a single time and file each of its words away. Query time is where you get paid back, over and over, for that one-time cost.

Two design choices earn their keep before we write a line. First, each posting will carry not just a document id but a term frequency -- how many times the word appears in that document -- because a later episode is going to rank results, and a word appearing eight times in a document is a stronger signal than appearing once. Second, and this is the load-bearing decision of the whole project: postings lists stay sorted by document id. Sorted lists are what make two of them intersectable in a single linear pass, which is the entire trick behind multi-word queries. Keep that in mind -- almost everything good downstream falls out of it.

Tokenizing text into terms

Before we can index words we have to cut text into words, and "word" needs a definition the machine can follow. Ours is deliberately simple: a run of letters or digits is a term, everything else is a separator, and we lowercase as we go so that "Zig", "ZIG" and "zig" all collapse to the same term. Here is a tokenizer built as an iterator -- the exact next() ?T shape from episode 23:

fn isTermChar(c: u8) bool {
    return (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or (c >= '0' and c <= '9');
}

const Tokenizer = struct {
    text: []const u8,
    pos: usize = 0,
    buf: [64]u8 = undefined,

    // NB: the returned slice is valid only until the NEXT call to next().
    fn next(self: *Tokenizer) ?[]const u8 {
        while (self.pos < self.text.len and !isTermChar(self.text[self.pos])) : (self.pos += 1) {}
        if (self.pos >= self.text.len) return null;
        const start = self.pos;
        while (self.pos < self.text.len and isTermChar(self.text[self.pos])) : (self.pos += 1) {}
        const raw = self.text[start..self.pos];
        const n = @min(raw.len, self.buf.len);
        for (raw[0..n], 0..) |c, i| self.buf[i] = std.ascii.toLower(c);
        return self.buf[0..n];
    }
};

fn lower(raw: []const u8, buf: []u8) []const u8 {
    const n = @min(raw.len, buf.len);
    for (raw[0..n], 0..) |c, i| buf[i] = std.ascii.toLower(c);
    return buf[0..n];
}

test "tokenizer lowercases and splits on punctuation" {
    var tok = Tokenizer{ .text = "Hello, WORLD! zig_lang 42" };
    try std.testing.expectEqualStrings("hello", tok.next().?);
    try std.testing.expectEqualStrings("world", tok.next().?);
    try std.testing.expectEqualStrings("zig", tok.next().?);
    try std.testing.expectEqualStrings("lang", tok.next().?);
    try std.testing.expectEqualStrings("42", tok.next().?);
    try std.testing.expect(tok.next() == null);
}

There is one sharp edge here that I want to hold up rather than hide, because it is the recurring gotcha of iterator-plus-scratch-buffer designs. The lowercased term is written into self.buf, an internal fixed buffer, and the slice we hand back points into it. That means the returned slice is only good until the next next() call, which reuses the same buffer. As long as you consume each term immediately -- and we will, by copying it into the index the instant we get it -- this is perfectly safe and allocation-free. Treat the returned slice as a borrow with a very short lease and you will never be bitten. (The lower helper does the same lowercasing on demand for query terms, where we do not have a running tokenizer.) Note also that zig_lang splits into two terms, since underscore is not a term char -- a definition you would tune per language, but this will do us fine.

The index structure

Now the index itself. A std.StringHashMap from term to postings list is the natural spine -- we met it back in episode 22 -- and each postings list is a sorted std.ArrayList of { doc, tf } pairs:

const Posting = struct { doc: u32, tf: u32 };

const Postings = struct {
    list: std.ArrayList(Posting) = .empty, // kept sorted by doc id
};

const Index = struct {
    gpa: std.mem.Allocator,
    map: std.StringHashMap(Postings),
    doc_count: u32 = 0,

    fn init(gpa: std.mem.Allocator) Index {
        return .{ .gpa = gpa, .map = std.StringHashMap(Postings).init(gpa) };
    }
    fn deinit(self: *Index) void {
        var it = self.map.iterator();
        while (it.next()) |e| {
            e.value_ptr.list.deinit(self.gpa); // free each postings list
            self.gpa.free(e.key_ptr.*);        // free the duped term string
        }
        self.map.deinit();
    }
};

The deinit deserves a slow read, because it exposes who owns what -- the question Zig forces you to answer out loud, and the reason its memory story is so much easier to trust than a language that hides it. A StringHashMap does not copy its keys; it stores the []const u8 slice you give it. If that slice points at transient memory (like our tokenizer's scratch buffer), the map is left holding a dangling pointer the moment that buffer is reused. So the index must own its term strings -- duplicate them on insert and free them here. We walk every entry, free the postings list, free the key, then tear down the map itself. Three lines, three distinct owners, all accounted for. On std.testing.allocator any slip shows up as a failed test, which is why every test in this episode runs leak-checked.

Adding a document

Indexing a document is one pass over its terms. For each term we find or create its postings list, then either start a fresh posting for this document or, if the word already appeared in this same document, bump the frequency on the posting we already have:

fn addDocument(self: *Index, text: []const u8) !u32 {
    const doc_id = self.doc_count;
    self.doc_count += 1;
    var tok = Tokenizer{ .text = text };
    while (tok.next()) |term| {
        const gop = try self.map.getOrPut(term);
        if (!gop.found_existing) {
            gop.key_ptr.* = self.gpa.dupe(u8, term) catch |err| {
                _ = self.map.remove(term); // keep the map consistent on OOM
                return err;
            };
            gop.value_ptr.* = .{};
        }
        const p = gop.value_ptr;
        const n = p.list.items.len;
        if (n > 0 and p.list.items[n - 1].doc == doc_id) {
            p.list.items[n - 1].tf += 1; // same doc again -> bump frequency
        } else {
            try p.list.append(self.gpa, .{ .doc = doc_id, .tf = 1 });
        }
    }
    return doc_id;
}

A few things are doing quiet, important work here. The getOrPut hands us a slot whether or not the term existed; on a new term we immediately overwrite key_ptr with an owned duplicate, because the term we looked up is that short-lease slice into the tokenizer's buffer and must never be what the map keeps. The catch |err| on the dupe is the honest handling of a mid-insert allocation failure -- if we cannot afford to own the key, we yank the half-formed entry back out with remove so the map is never left pointing at freed scratch memory, then bubble the error up. That is the kind of edge Zig makes you look straight at in stead of pretending it cannot happen.

And here is where the "sorted by doc id" promise pays for itself with zero effort. Because we index documents in id order (0, then 1, then 2...) and only ever append, each postings list comes out naturally sorted -- the newest posting always has the largest doc id, so it belongs at the end. We never sort a postings list; sortedness is a free consequence of the insertion order. The frequency bump is just as cheap: since all of a document's occurrences of a word are processed before we move to the next document, the matching posting -- if any -- is always the last one in the list. One comparison, no search.

Answering a single-word query

With the index built, the simplest query is a pure lookup, and it is worth writing the couple of helpers that read the structure back out:

fn postingsFor(self: *const Index, term_raw: []const u8) []const Posting {
    var buf: [64]u8 = undefined;
    const term = lower(term_raw, &buf);
    const e = self.map.get(term) orelse return &.{}; // absent word -> empty slice
    return e.list.items;
}

fn documentFrequency(self: *const Index, term_raw: []const u8) usize {
    return self.postingsFor(term_raw).len;
}

test "inverted index records postings and term frequency" {
    const gpa = std.testing.allocator;
    var index = Index.init(gpa);
    defer index.deinit();
    _ = try index.addDocument("the cat sat on the mat"); // doc 0, "the" appears twice
    _ = try index.addDocument("the dog sat");             // doc 1

    const the = index.postingsFor("the");
    try std.testing.expectEqual(@as(usize, 2), the.len); // present in two docs
    try std.testing.expectEqual(@as(u32, 0), the[0].doc);
    try std.testing.expectEqual(@as(u32, 2), the[0].tf); // twice in doc 0
    try std.testing.expectEqual(@as(usize, 2), index.documentFrequency("SAT")); // case-insensitive
    try std.testing.expectEqual(@as(usize, 0), index.documentFrequency("elephant"));
}

The lookup lowercases the query term the same way indexing did -- symmetry matters, or "SAT" would miss "sat" -- then either returns the postings slice or an empty slice for a word we have never seen. documentFrequency is a one-liner on top, but do not skip past it: the number of documents a word appears in is the quantity that decides how informative a word is when we start ranking. "the" appears everywhere and tells you almost nothing; a rare word appearing in three documents out of ten thousand is enormously discriminating. We are quietly gathering the raw material for that already.

Boolean AND: intersecting sorted postings

Single words are the warm-up. The query people actually type is several words, and they expect back the documents containing all of them -- "systems language" should return only documents holding both. In inverted-index terms that is the intersection of two postings lists, and because we kept both lists sorted by doc id, we can intersect them in a single linear walk with two pointers -- no nested loop, no hash set, no allocation beyond the result:

fn intersect(gpa: std.mem.Allocator, a: []const Posting, b: []const Posting) !std.ArrayList(u32) {
    var out: std.ArrayList(u32) = .empty;
    var i: usize = 0;
    var j: usize = 0;
    while (i < a.len and j < b.len) {
        if (a[i].doc < b[j].doc) {
            i += 1; // a is behind -> advance a
        } else if (a[i].doc > b[j].doc) {
            j += 1; // b is behind -> advance b
        } else {
            try out.append(gpa, a[i].doc); // equal -> a match, take it and advance both
            i += 1;
            j += 1;
        }
    }
    return out;
}

test "intersect helper on hand-built lists" {
    const gpa = std.testing.allocator;
    const a = [_]Posting{ .{ .doc = 1, .tf = 1 }, .{ .doc = 3, .tf = 1 }, .{ .doc = 5, .tf = 1 } };
    const b = [_]Posting{ .{ .doc = 2, .tf = 1 }, .{ .doc = 3, .tf = 1 }, .{ .doc = 5, .tf = 1 } };
    var out = try intersect(gpa, &a, &b);
    defer out.deinit(gpa);
    try std.testing.expectEqualSlices(u32, &.{ 3, 5 }, out.items);
}

This merge is the same maneuver that powers merging sorted runs, and it is only correct because the lists are sorted -- feed it unsorted postings and it silently returns garbage. That is the debt sortedness quietly repays. Whichever pointer is looking at the smaller doc id steps forward; when both point at the same id we have found a document in both lists, so we record it and advance both. Total work is the sum of the two list lengths, and not one byte of the original documents is touched.

For a full query we intersect all the terms' lists, and there is a lovely optimization that costs almost nothing: start from the rarest term -- the shortest postings list -- because the running intersection can only ever shrink, so seeding it with the smallest list keeps every subsequent merge as cheap as possible. If any query term is missing from the index entirely, the answer is immediately empty (nothing can contain a word we have never seen), and we bail out at once:

fn searchAnd(index: *const Index, gpa: std.mem.Allocator, query: []const u8) !std.ArrayList(u32) {
    var lists: std.ArrayList([]const Posting) = .empty;
    defer lists.deinit(gpa);
    var tok = Tokenizer{ .text = query };
    while (tok.next()) |term| {
        const p = index.postingsFor(term);
        if (p.len == 0) return .empty; // a missing term -> no doc holds ALL terms
        try lists.append(gpa, p);
    }
    if (lists.items.len == 0) return .empty;

    // rarest term first: the intersection only shrinks, so start from the smallest list
    std.mem.sort([]const Posting, lists.items, {}, struct {
        fn less(_: void, x: []const Posting, y: []const Posting) bool {
            return x.len < y.len;
        }
    }.less);

    var acc: std.ArrayList(u32) = .empty;
    for (lists.items[0]) |post| try acc.append(gpa, post.doc); // seed with the rarest term
    for (lists.items[1..]) |list| {
        var next_acc: std.ArrayList(u32) = .empty;
        var i: usize = 0;
        var j: usize = 0;
        while (i < acc.items.len and j < list.len) {
            if (acc.items[i] < list[j].doc) {
                i += 1;
            } else if (acc.items[i] > list[j].doc) {
                j += 1;
            } else {
                try next_acc.append(gpa, acc.items[i]);
                i += 1;
                j += 1;
            }
        }
        acc.deinit(gpa); // swap the old accumulator for the freshly intersected one
        acc = next_acc;
    }
    return acc;
}

test "boolean AND intersects sorted postings" {
    const gpa = std.testing.allocator;
    var index = Index.init(gpa);
    defer index.deinit();
    _ = try index.addDocument("zig is a systems language");      // 0
    _ = try index.addDocument("rust is a systems language");     // 1
    _ = try index.addDocument("python is a scripting language"); // 2
    _ = try index.addDocument("zig loves comptime");             // 3

    var r1 = try searchAnd(&index, gpa, "systems language");
    defer r1.deinit(gpa);
    try std.testing.expectEqualSlices(u32, &.{ 0, 1 }, r1.items); // both hold both words

    var r2 = try searchAnd(&index, gpa, "zig language");
    defer r2.deinit(gpa);
    try std.testing.expectEqualSlices(u32, &.{0}, r2.items); // only doc 0

    var r3 = try searchAnd(&index, gpa, "zig elephant");
    defer r3.deinit(gpa);
    try std.testing.expectEqual(@as(usize, 0), r3.items.len); // elephant is unknown
}

There is the search engine's beating heart. Four documents go in, and "systems language" comes back as {0, 1}, "zig language" as just {0}, and "zig elephant" as nothing at all -- each answer produced by lookups and linear merges, never by re-reading the documents. The accumulator dance (build next_acc, free the old acc, adopt the new one) is the one bit of memory bookkeeping to keep your eye on; get it wrong and you either leak the old buffer or read a freed one, and again the leak-checking allocator would rat you out on the spot.

How C, Rust, and Go do it

The inverted index is not a Zig curiosity -- it is the single most important data structure in information retrieval, and it looks much the same everywhere. In C, this is the shape underneath the classics: a hash table from term to a struct postings { uint32_t *docs; uint32_t *tf; size_t len, cap; }, grown by hand with realloc, and intersected with the identical two-pointer merge. The whole apparatus of Lucene -- the Java engine behind Elasticsearch and Solr -- is a wildly optimized version of exactly what we built, with the postings compressed (delta-encoded gaps plus variable-length integers) so that a list of millions of doc ids costs a couple of bits each. The C mindset is the same as ours here: own your buffers, keep them sorted, merge linearly.

In Rust, the natural spelling is HashMap<String, Vec<Posting>>, and the borrow checker is comfortable because there is no aliased graph anywhere -- just owned strings keying owned vectors. The intersection is often written as a slick iterator adaptor, but it compiles down to the same pointer walk. The tantivy crate is Rust's full-text search engine and is, once again, this structure wearing serious production armor. In Go, you would write map[string][]Posting and the same merge with sort.Search available when you want to gallop rather than step. Bleve is the Go equivalent. Four languages, one structure, one truth carried through all of them: index once so you can look up forever, and keep the postings sorted so multi-word queries are a linear merge in stead of a quadratic nightmare. Bam, jonguh ;-)

Where this is heading

Step back and look at what we have. Text goes in; a lookup structure comes out that answers "which documents hold this word" in time proportional to the answer, not the archive -- and answers "which documents hold all of these words" with a couple of linear merges. That is a real, working boolean search engine, small but honest, and every piece of it leaned on something we sharpened earlier in the series: the hash map, the sorted list, the iterator, the two-pointer merge.

But notice the quiet dissatisfaction hiding in those results. When "systems language" returned {0, 1}, we handed back two documents with no opinion about which one you would actualy rather read first. A real search box does not just find the matching documents -- it puts the best one at the top. And "best" is a surprisingly deep question: a word that shows up in every single document (like "the") should count for almost nothing, while a rare word that appears many times in one document should shove that document straight to the top. We have already been squirreling away the two numbers that answer this -- the term frequency on every posting, and the document frequency behind documentFrequency. Next time we put them to work and teach the engine not just to find, but to rank. That is where a pile of postings turns into something that feels like search ;-)

Thanks for reading, en tot de volgende keer! Go feed the index a few documents of your own and watch a two-word query resolve without ever re-reading a single one of them. De groeten! ;-)

@scipio

Leave Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index to:

Written by scipio

Does it matter who's right, or who's left?

Best Posts From scipio

We have not curated any of scipio's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.

Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index