DEV Community

Govindaraj Rangaraj
Govindaraj Rangaraj

Posted on Originally published at cheesedb.dev AI-assisted

A walk through the data structures (DSA) inside cheesedb.dev (a Go database engine for agentic memory)

Some use cases and implementation of data structures and algorithms inside CheeseDB, an embedded database for AI agent memory, written in Go with only the standard library. For each one the page says what it does, why it is there, what would break without it, and links to the exact lines on GitHub:

→ Topological sort for free: ids only go up, so id order already is one.
→ Kahn's in-degree trick: one counter per leg instead of rechecking every parent.
→ BFS with a queue: a recall walks down the graph, no recursion.
→ DP on a DAG: one pass in id order finds everything a crash left half-erased.
→ Min-heap: top-k search in about 30 lines.
→ Swap-remove: delete from a packed array in O(1).
→ Branch and bound: skip disk reads that a rounded score proves can't win.
→ Binary search: a lower bound over a sorted table.
→ Producer–consumer: one goroutine batches many writes into one fsync.

If you are learning DSA, the best next step is reading one real file. internal/ledger/state.go is about 300 lines: just the graph, no disk, no locks.

https://cheesedb.dev/inside.html

Top comments (0)