构建更好的图
让我们来解决前面发现的一些问题。顶点和边作为全局变量，意味着我们一次只能有一个图，这太受限了。为了解决这个问题，我们需要一些结构。先从命名空间开始：
Dagoba = {} // 命名空间我们用对象作为命名空间。JavaScript 里对象本质上就是无序的键值对集合。JS 只有四种基础数据结构，所以我们会经常用到对象。（可以在聚会时问问大家：“JS 的四种基础数据结构是什么？”）
现在我们需要图。可以用经典的 OOP 模式，但 JS 支持原型继承，所以我们可以先构建一个原型对象 Dagoba.G，再用工厂函数实例化它。这样做的好处是工厂可以返回不同类型的对象，而不是绑定到单一类构造器。
Dagoba.G = {} // 原型
Dagoba.graph = function(V, E) { // 工厂
var graph = Object.create(Dagoba.G)
graph.edges = []
graph.vertices = []
graph.vertexIndex = {}
graph.autoid = 1
if(Array.isArray(V)) graph.addVertices(V)
if(Array.isArray(E)) graph.addEdges(E)
return graph
}我们接受两个可选参数：顶点和边的列表。JS 对参数很宽容，未传递的参数默认是 undefined。通常我们会先有顶点和边再建图，但也可以后续动态添加。
接下来定义 addVertices 和 addEdges：
Dagoba.G.addVertices = function(vs) { vs.forEach(this.addVertex.bind(this)) }
Dagoba.G.addEdges = function(es) { es.forEach(this.addEdge .bind(this)) }这两个方法只是把工作交给了 addVertex 和 addEdge，我们继续定义它们：
Dagoba.G.addVertex = function(vertex) {
if(!vertex._id)
vertex._id = this.autoid++
else if(this.findVertexById(vertex._id))
return Dagoba.error('已存在该 ID 的顶点')
this.vertices.push(vertex)
this.vertexIndex[vertex._id] = vertex
vertex._out = []
vertex._in = []
return vertex._id
}如果顶点没有 _id，就分配一个自增 ID。如果已存在同 ID 顶点则报错。然后把顶点加入列表和索引，并初始化 _out 和 _in 属性。
Dagoba.G.addEdge = function(edge) {
edge._in = this.findVertexById(edge._in)
edge._out = this.findVertexById(edge._out)
if(!(edge._in && edge._out))
return Dagoba.error("该边的 in 或 out 顶点未找到")
edge._out._out.push(edge)
edge._in._in.push(edge)
this.edges.push(edge)
}首先查找边连接的两个顶点，若缺失则报错。然后把边加入两个顶点的出/入边列表，并加入图的边列表。
错误处理函数：
Dagoba.error = function(msg) {
console.log(msg)
return false
}到这里，基本的图结构就完成了！
进入查询
这个系统实际上只有两个部分：存储图的部分和回答图相关问题的部分。存储图的部分相当简单，正如我们所见。查询部分稍微复杂一些。
我们仍然从原型和查询工厂开始：
Dagoba.Q = {}
Dagoba.query = function(graph) { // 工厂
var query = Object.create(Dagoba.Q)
query.graph = graph // 图本身
query.state = [] // 每个步骤的状态
query.program = [] // 要执行的步骤列表
query.gremlins = [] // 每个步骤的小精灵
return query
}现在是介绍一些朋友的好时机。
一个程序是一系列步骤。每个步骤就像管道中的一段管子——数据从一端进入，经过某种转换，从另一端出去。我们的管道运行方式有所不同，但这是一个很好的初步近似。
程序中的每个步骤都可以有状态，query.state 是按步骤状态列表，索引与 query.program 中的步骤列表对应。
小精灵（gremlin）是在图中游走执行我们指令的生物。在数据库中发现小精灵可能令人惊讶，但它们可以追溯到 Tinkerpop 的 Blueprints，以及 Gremlin 和 Pacer 查询语言。它们记住去过的地方，让我们能够找到有趣问题的答案。
还记得我们想回答关于托尔二等表亲的问题吗？我们决定 Thor.parents.parents.parents.children.children.children 是一个很好的表达方式。每个 parents 或 children 实例都是程序中的一个步骤。每个步骤都包含对其管道类型（pipetype）的引用，这是执行该步骤操作的函数。
在我们的实际系统中，该查询可能看起来像：
g.v('Thor').out().out().out().in().in().in()
每个步骤都是一个函数调用，因此它们可以接受参数。解释器将步骤的参数传递给步骤的管道类型函数，所以在查询 g.v('Thor').out(2, 3) 中，out 管道类型函数将接收 [2, 3] 作为其第一个参数。
我们需要一种向查询添加步骤的方法。这里有一个辅助函数：
Dagoba.Q.add = function(pipetype, args) { // 向查询添加新步骤
var step = [pipetype, args]
this.program.push(step) // step 是管道类型和其参数的配对
return this
}每个步骤都是一个组合实体，将管道类型函数与应用于该函数的参数结合起来。我们可以在这个阶段将两者合并为一个部分应用的函数，而不是使用元组，但这样我们就会失去一些内省能力，这在后面会很有用。
我们将使用一小组查询初始化器从图生成新查询。这是启动大多数示例的 v 方法。它构建一个新查询，然后使用我们的 add 辅助器填充初始查询程序。这使用了 vertex 管道类型，我们稍后会看到。
Dagoba.G.v = function() { // 查询初始化器：g.v() -> query
var query = Dagoba.query(this)
query.add('vertex', [].slice.call(arguments)) // 向程序添加步骤
return query
}注意 [].slice.call(arguments) 是 JS 中"请给我这个函数参数数组"的说法。你可能以为 arguments 已经是数组了，因为它在许多情况下表现得像数组，但它缺少我们在现代 JavaScript 数组中使用的大部分功能。
急切求值的问题
在我们查看管道类型本身之前，我们要绕道探讨激动人心的执行策略世界。主要有两个学派：按值调用派（也称为急切派），严格坚持在应用函数之前评估所有参数。他们的对立派别是按需调用派，满足于拖延到最后可能的时刻才做任何事情——简而言之，他们是懒惰的。
JavaScript 是一种严格语言，会在调用时处理我们的每个步骤。因此我们期望 g.v('Thor').out().in() 的求值首先找到 Thor 顶点，然后找到通过出边连接到它的所有顶点，最后从这些顶点中的每一个返回它们通过入边连接的所有顶点。
在非严格语言中，我们会得到相同的结果——执行策略在这里没有太大区别。但如果我们添加更多调用呢？考虑到 Thor 的良好连接性，我们的 g.v('Thor').out().out().out().in().in().in() 查询可能产生许多结果——实际上，因为我们没有将顶点列表限制为唯一结果，它可能产生比图中总顶点数还要多的结果。
我们可能只对获得少数唯一结果感兴趣，所以我们稍微改变查询：g.v('Thor').out().out().out().in().in().in().unique().take(10)。现在我们的查询最多产生 10 个结果。但如果我们急切地求值会发生什么？我们仍然要在只返回前 10 个结果之前构建数万亿个结果。
所有图数据库都必须支持尽可能少做工作的机制，大多数选择某种形式的非严格求值来做到这一点。由于我们正在构建自己的解释器，我们程序的懒求值是可能的，但我们可能要应对一些后果。
求值策略对我们心智模型的影响
到目前为止，我们的求值心智模型非常简单：
- 请求一组顶点
- 将返回的集合作为输入传递给管道
- 根据需要重复
我们希望为用户保留这个模型，因为它更容易推理，但正如我们所看到的，我们不能再使用这个模型来实现。让用户在与实际实现不同的模型中思考是痛苦的根源。漏洞抽象是这种情况的小规模版本；在大范围内，它可能导致挫折、认知失调和愤怒退出。
不过，我们的情况几乎是这种欺骗的最佳状态：任何查询的答案都是相同的，无论执行模型如何。唯一的区别是性能。权衡是让所有用户在使用系统之前学习更复杂的模型，或者强制一部分用户从简单模型转向复杂模型，以便更好地推理查询性能。
在我们的情况下，这种权衡是有意义的。对于大多数用途，查询将返回足够快的结果，用户无需担心优化查询结构或学习更深层的模型。那些需要的用户是编写大型数据集高级查询的用户，他们也可能是最有能力转向新模型的用户。
管道类型
管道类型构成了我们系统的核心。一旦我们理解了每个类型的工作原理，我们就有了更好的基础来理解它们如何在解释器中被调用和排序。
我们先为管道类型创建一个位置，以及添加新类型的方法：
Dagoba.Pipetypes = {}
Dagoba.addPipetype = function(name, fun) { // 添加可链式方法
Dagoba.Pipetypes[name] = fun
Dagoba.Q[name] = function() {
return this.add(name, [].slice.apply(arguments)) // 捕获管道类型和参数
}
}管道类型的函数被添加到管道类型列表中，然后在查询对象上添加新方法。每个管道类型都必须有对应的查询方法。该方法向查询程序添加新步骤及其参数。
当我们求值 g.v('Thor').out('parent').in('parent') 时，v 调用返回查询对象，out 调用添加新步骤并返回查询对象，in 调用也做同样的事情。这就是启用我们方法链 API 的原因。
Dagoba.getPipetype = function(name) {
var pipetype = Dagoba.Pipetypes[name] // 管道类型是一个函数
if(!pipetype)
Dagoba.error('无法识别的管道类型：' + name)
return pipetype || Dagoba.fauxPipetype
}如果我们找不到管道类型，我们会生成错误并返回默认管道类型，它就像一个空导管：如果消息从一侧进来，它就从另一侧传递出去。
Dagoba.fauxPipetype = function(_, _, maybe_gremlin) { // 将结果传递到上游
return maybe_gremlin || 'pull' // 或向下游发送拉取
}Vertex
大多数我们遇到的管道类型会接受一个小精灵并产生更多小精灵，但这个特定的管道类型只从字符串生成小精灵。给定顶点 ID，它返回一个新的小精灵。给定查询，它会找到所有匹配的顶点，并逐个产生新的小精灵，直到处理完毕。
Dagoba.addPipetype('vertex', function(graph, args, gremlin, state) {
if(!state.vertices)
state.vertices = graph.findVertices(args) // 状态初始化
if(!state.vertices.length) // 全部完成
return 'done'
var vertex = state.vertices.pop() // 优化：需要顶点克隆
return Dagoba.makeGremlin(vertex, gremlin.state) // 来自 as/back 查询的小精灵
})我们首先检查是否已经收集了匹配的顶点，否则我们尝试找到一些。如果有任何顶点，我们将弹出一个并返回坐在该顶点上的新小精灵。每个小精灵都可以携带自己的状态，就像它在图中旅行时去过的地方和看到的有趣事物的日志。
In-N-Out
遍历图就像订购汉堡一样简单。这两行为我们设置了 in 和 out 管道类型：
Dagoba.addPipetype('out', Dagoba.simpleTraversal('out'))
Dagoba.addPipetype('in', Dagoba.simpleTraversal('in'))simpleTraversal 函数返回一个管道类型处理器，它接受小精灵作为输入，并在每次查询时生成新的小精灵。一旦这些小精灵用完，它就发回'pull'请求从其前任获取新的小精灵。
Dagoba.simpleTraversal = function(dir) {
var find_method = dir == 'out' ? 'findOutEdges' : 'findInEdges'
var edge_list = dir == 'out' ? '_in' : '_out'
return function(graph, args, gremlin, state) {
if(!gremlin && (!state.edges || !state.edges.length)) // 查询初始化
return 'pull'
if(!state.edges || !state.edges.length) { // 状态初始化
state.gremlin = gremlin
state.edges = graph[find_method](gremlin.vertex) // 获取匹配的边
.filter(Dagoba.filterEdges(args[0]))
}
if(!state.edges.length) // 没有更多工作要做
return 'pull'
var vertex = state.edges.pop()[edge_list] // 使用一条边
return Dagoba.gotoVertex(state.gremlin, vertex)
}
}Property
让我们暂停一下，考虑基于我们见过的三种管道类型的示例查询。我们可以像这样询问托尔的祖父母：
g.v('Thor').out('parent').out('parent').run()
但如果我们想要他们的名字呢？我们可以在末尾放一个 map：
g.v('Thor').out('parent').out('parent').run()
.map(function(vertex) {return vertex.name})但这是一个足够常见的操作，我们更喜欢写得更像：
g.v('Thor').out('parent').out('parent').property('name').run()
Dagoba.addPipetype('property', function(graph, args, gremlin, state) {
if(!gremlin) return 'pull' // 查询初始化
gremlin.result = gremlin.vertex[args[0]]
return gremlin.result == null ? false : gremlin // 错误属性返回 false
})Unique
如果我们想收集托尔祖父母的所有孙子——他的表兄弟、兄弟姐妹和他自己——我们可以做这样的查询：g.v('Thor').in().in().out().out().run()。然而，这会给我们很多重复项。
为了解决这个问题，我们引入一个名为'unique'的新管道类型：
g.v('Thor').in().in().out().out().unique().run()
Dagoba.addPipetype('unique', function(graph, args, gremlin, state) {
if(!gremlin) return 'pull' // 查询初始化
if(state[gremlin.vertex._id]) return 'pull' // 拒绝重复
state[gremlin.vertex._id] = true
return gremlin
})Filter
我们已经看到了两种简单的过滤方式，但有时我们需要更复杂的约束。如果我们想找到托尔的所有体重大于身高的兄弟姐妹怎么办？
g.v('Thor').out().in().unique()
.filter(function(asgardian) { return asgardian.weight > asgardian.height })
.run()Dagoba.addPipetype('filter', function(graph, args, gremlin, state) {
if(!gremlin) return 'pull' // 查询初始化
if(typeof args[0] == 'object') // 按对象过滤
return Dagoba.objectFilter(gremlin.vertex, args[0])
? gremlin : 'pull'
if(typeof args[0] != 'function') {
Dagoba.error('过滤器不是函数：' + args[0])
return gremlin // 保持运行
}
if(!args[0](gremlin.vertex, gremlin)) return 'pull' // 小精灵未通过过滤器
return gremlin
})Take
我们并不总是想要一次性获得所有结果。有时我们只需要少数几个结果：
g.v('Thor').out().out().out().out().in().in().in().in().unique().take(12).run()
没有 take 管道，该查询可能需要很长时间才能运行，但由于我们的懒求值策略，带有 take 管道的查询非常高效。
Dagoba.addPipetype('take', function(graph, args, gremlin, state) {
state.taken = state.taken || 0 // 状态初始化
if(state.taken == args[0]) {
state.taken = 0
return 'done' // 全部完成
}
if(!gremlin) return 'pull' // 查询初始化
state.taken++
return gremlin
})As
这接下来的四个管道类型作为一个组工作，允许更高级的查询。这个只是让你标记当前顶点。我们将在接下来的两个管道类型中使用该标签。
Dagoba.addPipetype('as', function(graph, args, gremlin, state) {
if(!gremlin) return 'pull' // 查询初始化
gremlin.state.as = gremlin.state.as || {} // 初始化 'as' 状态
gremlin.state.as[args[0]] = gremlin.vertex // 将标签设置为顶点
return gremlin
})Merge
一旦我们标记了顶点，我们就可以使用 merge 提取它们。如果我们想要托尔的父母、祖父母和曾祖父母，我们可以这样做：
g.v('Thor').out().as('parent').out().as('grandparent').out().as('great-grandparent')
.merge('parent', 'grandparent', 'great-grandparent').run()Dagoba.addPipetype('merge', function(graph, args, gremlin, state) {
if(!state.vertices && !gremlin) return 'pull' // 查询初始化
if(!state.vertices || !state.vertices.length) { // 状态初始化
var obj = (gremlin.state||{}).as || {}
state.vertices = args.map(function(id) {return obj[id]}).filter(Boolean)
}
if(!state.vertices.length) return 'pull' // 这批完成
var vertex = state.vertices.pop()
return Dagoba.makeGremlin(vertex, gremlin.state)
})Except
我们已经看到了想说"给我所有不是托尔的托尔兄弟姐妹"的情况。使用 as 和 except 更直接：
g.v('Thor').as('me').out().in().except('me').unique().run()
Dagoba.addPipetype('except', function(graph, args, gremlin, state) {
if(!gremlin) return 'pull' // 查询初始化
if(gremlin.vertex == gremlin.state.as[args[0]]) return 'pull'
return gremlin
})Back
有些我们可能问的问题涉及进一步检查图，只是为了在答案是肯定的情况下稍后返回到我们的起始点。
g.v('Fjörgynn').in().as('me') // 第一个小精灵的 state.as 是 Frigg
.in() // 第一个小精灵的顶点现在是 Baldr
.out().out() // 为每个祖父母克隆该小精灵
.filter({_id: 'Bestla'}) // 只保留祖父母 Bestla 上的小精灵
.back('me').unique().run() // 将小精灵的顶点跳回 Frigg 并退出Dagoba.addPipetype('back', function(graph, args, gremlin, state) {
if(!gremlin) return 'pull' // 查询初始化
return Dagoba.gotoVertex(gremlin, gremlin.state.as[args[0]])
})辅助函数
上面的管道类型依赖一些辅助函数来完成它们的工作。让我们在深入解释器之前快速看一下这些。
小精灵
小精灵是简单的生物：它们有一个当前顶点和一些本地状态。所以要创建一个新的，我们只需要创建一个具有这两样东西的对象。
Dagoba.makeGremlin = function(vertex, state) {
return {vertex: vertex, state: state || {} }
}我们也可以取一个现有的小精灵并将其发送到新顶点：
Dagoba.gotoVertex = function(gremlin, vertex) { // 克隆小精灵
return Dagoba.makeGremlin(vertex, gremlin.state)
}查找
vertex 管道类型使用 findVertices 函数从中收集一组初始顶点来开始我们的查询。
Dagoba.G.findVertices = function(args) { // 顶点查找器辅助函数
if(typeof args[0] == 'object')
return this.searchVertices(args[0])
else if(args.length == 0)
return this.vertices.slice() // 优化：切片代价高昂
else
return this.findVerticesByIds(args)
}Dagoba.G.findVerticesByIds = function(ids) {
if(ids.length == 1) {
var maybe_vertex = this.findVertexById(ids[0]) // 也许它是一个顶点
return maybe_vertex ? [maybe_vertex] : [] // 或者也许不是
}
return ids.map( this.findVertexById.bind(this) ).filter(Boolean)
}
Dagoba.G.findVertexById = function(vertex_id) {
return this.vertexIndex[vertex_id]
}Dagoba.G.searchVertices = function(filter) { // 匹配过滤器的属性
return this.vertices.filter(function(vertex) {
return Dagoba.objectFilter(vertex, filter)
})
}过滤
我们看到 simpleTraversal 在遇到的边上使用过滤函数。这是一个简单但强大的函数：
Dagoba.filterEdges = function(filter) {
return function(edge) {
if(!filter) // 无过滤器：一切都有效
return true
if(typeof filter == 'string') // 字符串过滤器：标签必须匹配
return edge._label == filter
if(Array.isArray(filter)) // 数组过滤器：必须包含标签
return !!~filter.indexOf(edge._label)
return Dagoba.objectFilter(edge, filter) // 对象过滤器：检查边键
}
}Dagoba.objectFilter = function(thing, filter) {
for(var key in filter)
if(thing[key] !== filter[key])
return false
return true
}解释器的本质
我们已经到达了叙事山的顶峰，准备接收我们的奖品：解释器。代码实际上相当紧凑，但模型有一些微妙之处。
我们之前将程序比作管道，这是编写查询的好心智模型。但正如我们所看到的，我们需要一个不同的模型来实际实现。该模型更像图灵机而不是管道：有一个读/写头坐在特定步骤上。它"读取"步骤，改变其"状态"，然后向左或向右移动。
解释器揭晓
Dagoba.Q.run = function() { // 查询处理的机器
var max = this.program.length - 1 // 程序中最后一步的索引
var maybe_gremlin = false // 小精灵、信号字符串或 false
var results = [] // 这次运行的结果
var done = -1 // 已完成的事情后面
var pc = max // 我们的程序计数器
var step, state, pipetype
while(done < max) {
var ts = this.state
step = this.program[pc] // step 是管道类型和参数的配对
state = (ts[pc] = ts[pc] || {}) // 这一步的状态必须是对象
pipetype = Dagoba.getPipetype(step[0]) // 管道类型只是一个函数
maybe_gremlin = pipetype(this.graph, step[1], maybe_gremlin, state)
if(maybe_gremlin == 'pull') { // 'pull' 意味着管道想要更多输入
maybe_gremlin = false
if(pc-1 > done) {
pc-- // 尝试前一个管道
continue
} else {
done = pc // 前一个管道完成了，所以我们也完成了
}
}
if(maybe_gremlin == 'done') { // 'done' 告诉我们管道已完成
maybe_gremlin = false
done = pc
}
pc++ // 移动到下一个管道
if(pc > max) {
if(maybe_gremlin)
results.push(maybe_gremlin) // 小精灵从管道中弹出
maybe_gremlin = false
pc-- // 退一步
}
}
results = results.map(function(gremlin) { // 返回投影结果或顶点
return gremlin.result != null
? gremlin.result : gremlin.vertex } )
return results
}查询转换器
现在我们有了一个很好的紧凑的查询程序解释器，但我们仍然缺少一些东西。每个现代数据库管理系统都带有查询优化器作为系统的重要组成部分。
Dagoba.T = [] // 转换器
Dagoba.addTransformer = function(fun, priority) {
if(typeof fun != 'function')
return Dagoba.error('无效的转换器函数')
for(var i = 0; i < Dagoba.T.length; i++) // 优化：二分搜索
if(priority > Dagoba.T[i].priority) break
Dagoba.T.splice(i, 0, {priority: priority, fun: fun})
}要运行这些转换器，我们将在解释器顶部注入一行代码：
Dagoba.Q.run = function() { // 我们的查询虚拟机
this.program = Dagoba.transform(this.program) // 激活转换器
// ...existing code...
}Dagoba.transform = function(program) {
return Dagoba.T.reduce(function(acc, transformer) {
return transformer.fun(acc)
}, program)
}别名
进行像 g.v('Thor').out().in() 这样的查询是相当紧凑的，但这是托尔的兄弟姐妹还是他的伴侣？两种解释都不完全令人满意。说出我们的意思会更好：g.v('Thor').parents().children() 或 g.v('Thor').children().parents()。
我们可以使用查询转换器和几个额外的辅助函数来制作别名：
Dagoba.addAlias = function(newname, oldname, defaults) {
defaults = defaults || [] // 别名的默认参数
Dagoba.addTransformer(function(program) {
return program.map(function(step) {
if(step[0] != newname) return step
return [oldname, Dagoba.extend(step[1], defaults)]
})
}, 100) // 100 因为别名早期运行
Dagoba.addPipetype(newname, function() {})
}Dagoba.extend = function(list, defaults) {
return Object.keys(defaults).reduce(function(acc, key) {
if(typeof list[key] != 'undefined') return acc
acc[key] = defaults[key]
return acc
}, list)
}现在我们可以制作我们想要的别名：
Dagoba.addAlias('parents', 'out')
Dagoba.addAlias('children', 'in')性能
所有生产图数据库都有一个特定的性能特征：图遍历查询相对于总图大小是常数时间。在非图数据库中，询问某人的朋友列表可能需要与条目数量成比例的时间，因为在朴素的最坏情况下，你必须查看每个条目。
图数据库通过在顶点和边之间建立直接连接来避开这个问题，所以图遍历只是指针跳转；无需扫描每个项目，无需索引，根本不需要额外工作。现在无论图中的总人数如何，查找你的朋友都有相同的价格，没有额外的空间成本或写入时间成本。
我们可以在 Dagoba 的小宇宙中看到这一点，如果我们替换查找边的函数。这是一个朴素版本，在线性时间内搜索所有边：
Dagoba.G.findInEdges = function(vertex) {
return this.edges.filter(function(edge) {return edge._in._id == vertex._id} )
}
Dagoba.G.findOutEdges = function(vertex) {
return this.edges.filter(function(edge) {return edge._out._id == vertex._id} )
}这是我们的老朋友：纯粹、甜美的无索引邻接：
Dagoba.G.findInEdges = function(vertex) { return vertex._in }
Dagoba.G.findOutEdges = function(vertex) { return vertex._out }序列化
在内存中有图很棒，但我们首先如何获得它？我们看到图构造函数可以接受顶点和边的列表并为我们创建图，但一旦构建了图，我们如何重新获得顶点和边？
我们的自然倾向是做类似 JSON.stringify(graph) 的事情，这会产生非常有用的错误"TypeError: Converting circular structure to JSON"。在图构建过程中，顶点链接到它们的边，边都链接到它们的顶点，所以现在一切都相互引用。
Dagoba.jsonify = function(graph) {
return '{"V":' + JSON.stringify(graph.vertices, Dagoba.cleanVertex)
+ ',"E":' + JSON.stringify(graph.edges, Dagoba.cleanEdge)
+ '}'
}这些是顶点和边的替换器：
Dagoba.cleanVertex = function(key, value) {
return (key == '_in' || key == '_out') ? undefined : value
}
Dagoba.cleanEdge = function(key, value) {
return (key == '_in' || key == '_out') ? value._id : value
}持久化
持久化通常是数据库最棘手的部分之一：磁盘相对安全但速度慢。批处理写入、使它们原子化、日志记录——这些很难做到既快又正确。
幸运的是，我们正在构建一个内存数据库，所以我们不必担心任何这些！不过，我们可能偶尔想要在本地保存数据库副本以便在页面加载时快速重启。
Dagoba.G.toString = function() { return Dagoba.jsonify(this) }Dagoba.fromString = function(str) { // 另一个图构造函数
var obj = JSON.parse(str) // 这可能抛出异常
return Dagoba.graph(obj.V, obj.E)
}现在我们将在持久化函数中使用这些：
Dagoba.persist = function(graph, name) {
name = name || 'graph'
localStorage.setItem('DAGOBA::'+name, graph)
}
Dagoba.depersist = function (name) {
name = 'DAGOBA::' + (name || 'graph')
var flatgraph = localStorage.getItem(name)
return Dagoba.fromString(flatgraph)
}更新
我们的 out 管道类型复制顶点的出边并在每次需要时弹出一个。构建新数据结构需要时间和空间，并对内存管理器施加更多工作。我们本可以直接使用顶点的出边列表，用计数器变量跟踪我们的位置。你能想到这种方法的问题吗？
如果有人在我们查询中间删除了我们访问过的边，那会改变我们边列表的大小，然后我们会跳过一条边，因为我们的计数器会偏移。为了解决这个问题，我们可以锁定查询中涉及的顶点，但这样我们要么失去定期更新图的能力，要么失去让长期查询对象按需响应更多结果请求的能力。
未来方向
我们之前看到了一种收集祖先的方法：
g.v('Thor').out().as('parent')
.out().as('grandparent')
.out().as('great-grandparent')
.merge(['parent', 'grandparent', 'great-grandparent'])
.run()这相当笨拙，并且不能很好地扩展——如果我们想要六层祖先怎么办？或者查看任意数量的祖先直到我们找到我们想要的？
如果我们能说类似这样的话会很好：
g.v('Thor').out().all().times(3).run()
总结
那么我们学到了什么？图数据库非常适合存储您计划通过图遍历查询的互连数据。添加非严格语义允许对查询使用流畅的接口，出于性能原因，您永远无法在急切系统中表达这些查询，并允许您跨越异步边界。时间使事情变得复杂，来自多个角度的时间（即并发）使事情变得非常复杂，所以每当我们可以避免引入时间依赖性（例如状态、可观察效果等）时，我们就会使推理我们的系统变得更容易。
以简单、解耦和极其未优化的风格构建为以后的全局优化留下了大门，使用驱动程序循环允许正交优化——每个都不引入大多数优化技术标志的脆弱性和复杂性。
最后一点不能被夸大：保持简单。避免优化而支持简单性。通过找到正确的模型来努力实现简单性。探索许多可能性。本书中的章节提供了充分的证据，表明高度非平凡的应用程序可以有一个小而紧密的内核。一旦你为正在构建的应用程序找到那个内核，就要努力防止复杂性污染它。构建用于附加额外功能的钩子，并不惜一切代价维护您的抽象屏障。
Dagoba：一个内存图数据库
作者：Dann Toliver
“当我们试图单独挑出任何事物时，我们会发现它被成千上万根看不见的线牢牢地绑在宇宙中的一切之上，无法分割。”——约翰·缪尔
“走向世界尽头的，不是它自己，上帝、太阳、莎士比亚、推销员，实际上都已穿越自身，最终成为了那个自我。”——詹姆斯·乔伊斯
序幕
很久以前，当世界还很年轻时，所有数据都乖乖地排成一行。如果你想让数据跳过一道篱笆，只需把篱笆放在它们前面，每个数据就会依次跳过去。打孔卡进，打孔卡出。生活简单，编程轻松。
后来，随机访问的革命到来了，数据开始在山坡上自由地游荡。如何管理这些数据成了大问题：既然你可以随时访问任何一条数据，下一步该选哪一条？于是人们发明了通过建立数据之间的链接来管理数据的方法，把数据组装成队列。提问时，只需挑一只羊，把与它相连的所有数据都拉出来。
后来，程序员们又制定了一套新的数据聚合规则。他们不再直接把不同的数据绑在一起，而是按内容聚类，把数据拆分成小块，收集到围栏里，并贴上标签。查询以声明式的方式提出，结果是把部分分解的数据片段（关系型数据库称之为“规范化”）拼凑成一个集合返回给程序员。
在很长一段时间里，关系模型一直占据主导地位。它在两次主要的语言战争和无数次小冲突中都未被撼动。它几乎满足了你对模型的所有需求，代价只是低效、笨拙和不易扩展。很长时间里，程序员们都愿意为此买单。直到互联网的出现。
分布式革命再次改变了一切。数据突破了空间的限制，在不同机器间自由流动。理论家们用 CAP 原则打破了关系型数据库的垄断，开启了新的数据管理方式——其中有些方式甚至回归了最早的随机访问数据管理尝试。我们要介绍的，就是其中一种：图数据库。
初探
在本章中，我们将构建一个图数据库。在构建过程中，我们会探索问题空间，为设计决策生成多种方案，比较这些方案，理解它们之间的权衡，最终为我们的系统选择合适的方案。我们会特别关注代码的简洁性，但整体过程与专业软件开发并无二致。本章的目的是教会你这种开发流程，并最终构建一个图数据库。
使用图数据库可以优雅地解决一些有趣的问题。图是一种非常自然的数据结构，适合探索事物之间的联系。这里的“图”指的是一组顶点和一组边，也就是一堆点和连接它们的线。而“数据库”？数据库就像是数据的堡垒，你把数据放进去，再把数据取出来。
那么，图数据库能解决哪些问题？假设你喜欢追踪家谱：父母、祖父母、远房表亲等等。你希望开发一个系统，可以自然优雅地查询“托尔的二等表亲是谁？”或“芙蕾雅与女武神之间有什么联系？”
一个合理的结构是有一个实体表和一个关系表。比如查询托尔的父母：
SELECT e.* FROM entities as e, relationships as r
WHERE r.out = "Thor" AND r.type = "parent" AND r.in = e.id但如果要查祖父母呢？你需要子查询，或者用 SQL 的厂商扩展。等到查二等表亲时，SQL 语句会变得非常冗长。
我们理想的查询方式是什么？既简洁又灵活，能自然表达查询意图，并能扩展到类似的查询。second_cousins('Thor') 很简洁，但不够灵活。上面的 SQL 很灵活，但不够简洁。
像 Thor.parents.parents.parents.children.children.children 这样的表达方式，兼顾了简洁和灵活。虽然这样写会包含太多结果（包括一等表亲和兄弟姐妹），但整体思路是对的。
我们能构建出怎样的最简单的系统，来实现这种接口？我们可以像关系型数据库那样，维护顶点和边的列表，然后写一些辅助函数。例如：
V = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
E = [ [1,2], [1,3], [2,4], [2,5], [3,6], [3,7], [4,8]
, [4,9], [5,10], [5,11], [6,12], [6,13], [7,14], [7,15] ]
parents = function(vertices) {
var accumulator = []
for(var i=0; i < E.length; i++) {
var edge = E[i]
if(vertices.indexOf(edge[1]) !== -1)
accumulator.push(edge[0])
}
return accumulator
}上述函数的本质是遍历列表，对每个元素执行代码，并累加结果。其实可以更简洁，比如用 reduce：
parents = (vertices) => E.reduce( (acc, [parent, child])
=> vertices.includes(child) ? acc.concat(parent) : acc , [] )
children = (vertices) => E.reduce( (acc, [parent, child])
=> vertices.includes(parent) ? acc.concat(child) : acc , [] )这样我们就可以写：
children(children(children(parents(parents(parents([8]))))))
虽然括号有点多，但已经很接近我们想要的效果了。