Index-free adjacency: follow pointers

1def expand_one_hop(node):
2    # follow 1: node record stores the address of its first rel
3    rel = deref(node.firstRel)        # land ON the rel record
4    # follow 2: read the rel record (a precomputed join, baked in)
5    end_addr = rel.endNode            # the address it points at
6    # follow 3: dereference that to land ON the neighbor node
7    neighbor = deref(end_addr)        # 3 follows total, no index
8    return neighbor                    # O(1), independent of N

1def expand_one_hop(user_id):
2    # no stored pointer — search the index for the join row
3    rows = btree_seek(USER_FRIEND, key=user_id)
4    # seek descends ceil(log_fanout(N)) levels — grows with the table
5    neighbors = [r.friend_id for r in rows]
6    return neighbors                   # O(log N), grows with size

1def k_hop(start, k=5):
2    frontier = {start}
3    for _ in range(k):              # one level per hop
4        next = set()
5        for node in frontier:
6            # each expand is the 3-follow O(1) hop, no index
7            next |= expand_one_hop(node)
8        frontier = next
9    return frontier                  # cost ~ nodes reached, not N

1def k_hop(start_id, k=5):
2    frontier = {start_id}
3    for _ in range(k):              # one self-join per hop
4        next = set()
5        for uid in frontier:
6            # no stored pointer — seek the join index each time
7            next |= btree_seek(USER_FRIEND, key=uid)
8        frontier = next
9    return frontier   # k x O(log N) — grows as the table grows