我正处于为 C++ 设计基于图形(或键值)的数据库库的准备阶段，这里的许多人会发现类似于 http://neo4j.org/ 等项目。 .
由于这是一个非常早期的设计阶段，我的要求很简单，未经提炼，而且(我承认)可能仍然相当幼稚:
- 有向无环图
- 根少叶多的树状结构
- 分支可能包含对其他分支的引用
- 但没有循环
- 该图由键值对表示，其中键和值大部分是简单类型(整数)，但有些可能指更复杂的类型，例如字符串
- 查询
- 简单的查询通常会返回边。 IE。从此根开始的哪些边对应于(键/值/键值元组)？
- 使用键字符串(键、键、键、值)进行查询
- 访问模式和性能
- 应强调快速查找
- 添加边
- 但没有从图中删除边/节点。 IE。该图会增长，但永远不会缩小。
- 可以对图进行优化，以优化缓存使用的内存布局
- 图表的大小大约为 1 MB - 2 GB，并且大部分应该适合主内存
鉴于这些粗略的要求是一项挑战，您最关心的是:
- 内存存储:布局、分配
- 例如固定大小的 block 池？
- 通过聚类算法分配内存？
- 快速查询
- 动态重组
- 如何处理边/节点的添加？
- 优化更新(例如改进内存布局)
- 并发访问
- 例如通过优化线程处理内存布局的更改？
我正在寻找良好的起点来工作，因此我非常高兴收到对现有工作的引用。 最重要的是:我应该思考什么是我没有思考的？
最佳答案
But no cycles
如果您需要快速刃口插入，这是一个很高的要求。在最坏的情况下(其中 v 是顶点数，e 是边数)，验证新边不会引入循环是 O(v+e)。它也可能排除边的并发插入。考虑将此要求设为可选。
另一种选择是区分两个插入操作:CheapInsert 和 ExpensiveInsert。让每个顶点都有一个“等级”整数，并且只允许从较低等级的顶点到较高等级的顶点进行廉价的边插入。昂贵的插入将没有此约束，并会在必要时自动重写行列。客户端可以检查和更改任何顶点的等级(只要不破坏从低到高的规则)。通过这种方式，他们可以实现自己的插入策略，可能是通过利用图的某些特定属性来避免昂贵的插入。
关于c++ - 基于图形(键/值)数据库的面向性能的设计，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1370610/