Build your own knowledge graph database
Label & property indexes·10 min

Build a property index

0 / 1
# grade this stage (from your course directory)
npx theinference test --stage property-index --watch

Add a hash index on (label, key, value) so finding "the Person named Tom Hanks" is O(1), not a scan. Build Map<label, Map<key, Map<taggedValue, Set<nodeId>>>> at load; findNodes does three hash lookups.

Your task

Implement findNodes

Index every property of every node, scoped by label. findNodes(label, key, value) returns the sorted matching ids. The CLI's find Person name 'Tom Hanks' prints [10].

src/store.ts
function tagValue(v: Value): string {
  if (Array.isArray(v)) return "a:" + JSON.stringify(v);
  if (typeof v === "number") return "n:" + v;
  if (typeof v === "boolean") return "b:" + v;
  return "s:" + v;
}

findNodes(label: string, key: string, value: Value): number[] {
  const ids = this.propIndex.get(label)?.get(key)?.get(tagValue(value));
  return ids ? [...ids].sort((a, b) => a - b) : [];
}
Process command
your_program.sh find {fixture}/fixtures/data/nodes.json {fixture}/fixtures/data/relationships.json Person name "Tom Hanks"
# -> [10]
Tag the value with its type

released: 1999 (int) and a hypothetical name: '1999' (string) must not collide in the index. Serialize the value with a type tag (n:1999 vs s:1999) before using it as a map key. Graphs are schema-free, so the same raw value can appear as different types under different keys.

How it's graded

Process mode, stdout_json_match against [10]. A name that doesn't exist must return []. The index is scoped by label, so findNodes('Movie', 'name', ...) never matches a Person.

Build the label indexIndex trade-offs