如何用 Python 实现一个图数据库（Graph Database）

作者：流光飞舞来源：https://shuhari.dev/blog/2022/02/500lines-rewrite-dagoba

本文章是 重写 500 Lines or Less 系列的其中一篇，目标是重写 500 Lines or Less 系列的原有项目：Dagoba: an in-memory graph database。

背景

Dagoba 是作者设计用来展示如何从零开始自己实现一个图数据库（Graph Database）。该名字似乎来源于作者喜欢的一个乐队，另一个原因是它的前缀 DAG 也正好是有向无环图 （Directed Acyclic Graph） 的缩写。本文也沿用了该名称。

图是一种常见的数据结构，它将信息描述为若干独立的节点（vertex，为了和下文的边更加对称，本文中称为 node），以及把节点关联起来的边（edge）。我们熟悉的链表以及多种树结构可以看作是符合特定规则的图。图在路径选择、推荐算法以及神经网络等方面都是重要的核心数据结构。

既然图的用途如此广泛，一个重要的问题就是如何存储它。如果在传统的关系数据库中存储图，很自然的做法就是为节点和边各自创建一张表，并用外键把它们关联起来。这样的话，要查找某人所有的子女，就可以写下类似下面的查询：

select nodes.* from nodes, edges
on nodes.id=edges.in
where nodes.name='Jack' and edges.type='child'