2

由于我使用的是 PostgreSQL，因此有一个名为ltree的模块，它至少满足了我的一个需求，即性能（我不知道可伸缩性？有人说物化路径树不能很好地伸缩......）。

由于我正在开发的应用程序是一个完全围绕一棵大树、节点、子树等构建的 CMS，因此在对这些节点进行排队时，性能是绝对必要的，但由于它是一个分层的大树（随着它的增长），你正在处理和操作GUI（CRUD），我还想让用户在正确更新数据库中的树（子记录）的同时拖放以重新排序节点、子树等。

据我了解，在树中移动和重新排序节点/子树并不是 ltree/物化路径树的真正用途，所以我希望你能帮助我指出正确的树结构模型是最好的为了性能和移动子树和节点，或者……如果 ltree 确实不是过去的遗留物，但仍然值得使用，你如何使用 PostgreSQL 的 ltree 模块来实现这一点？在这种情况下为什么/为什么不使用 ltree？

要求：

  1. 查询性能当然是我的首要任务（所有节点、子树、叶子）。
  2. 树应该支持深层嵌套和排序
  3. 当然，树应该支持变大和扩展
  4. 如果不存在 1 个“万事通”树实现，或者太复杂而不值得，我可以在从 GUI 重新排序时忍受一点等待时间。

我也在考虑闭包表，也就是桥表（很多！），嵌套间隔（不确定我是否完全理解如何实现它，目前没有好的例子或要点？）或 B-tree 模型。我只是不太确定，这些将如何满足我的上述 4 个要求。以嵌套间隔重新组织子树和节点似乎很简单，性能似乎也不错。很难选择合适的。

因为我肯定需要性能（查询/读取性能）、可伸缩性、排序，所以我有点认为带有排序顺序的闭包表可能非常接近，但我无法想象闭包表和磁盘空间开销会变成我的树有多大节点变大。闭包表和可扩展性，我不太确定。我担心这个问题有错吗？这项任务的最佳解决方案可能是什么？

4

1 回答 1

4

用于索引存储在 SQL 中的树的典型数据结构针对不经常更改的集合的读取性能进行了设计和优化。

例如，如果您使用嵌套集模型，添加或删除节点将涉及更新整个树（这通常意味着重写整个表）：非常适合读取，而不适合写入。

当写入性能对您很重要时，您通常最好(id, parent_id)使用递归查询处理原始元组，同时将您肯定知道的树索引设置为空值。在应用程序中读取性能更重要的区域中，通过检查树索引中的空值来进行完整性检查，并在实际使用树之前根据需要重新索引树。这样，您将避免不断地重写您的树，而是仅在需要读取时重新索引它。

另一种虽然（更）困难的方法是使用嵌套集或嵌套间隔的变体，但使用实数或浮点数而不是整数。这允许免费插入、移动和删除节点，但代价是一些存储和算术/读取开销以及一些属性的丢失，例如嵌套集的子节点计数。但是，它还要求您留意病态的边缘情况。也就是说，当您遇到浮点类型的精度限制时，您需要定期（有时​​是先发制人）“垃圾收集”并重新索引树索引的足够大块，以便适应新节点。

（后者的一种变体是使用没有任何精度的数字来试图躲避这个问题。但它实际上是在把罐子踢下去，因为你仍然会受到几千个 Postgres 内部结构的限制精度数字。与几年前在我自己的测试中遇到该限制之前，仅使用浮点类型相比，存储和算术开销就变得很重要。）

至于“最佳”结构或方法，真的没有灵丹妙药......根据用例（读取与写入的频率）和集合的大小，每个都有优缺点。网络上有大量文献对它们进行了比较和解释，我相信你已经找到了。

话虽如此，对于 CMS，我建议您使用您最熟悉的任何方法。要么在写入发生时动态地重新索引树，要么在写入时将树标记为脏，然后根据需要重新索引它。这里的重点是，如果重新索引正确完成（= 使用 plpgsql 函数或等效函数，而不是您的应用程序发出的大量查询），重新索引几十万节点的整个树将需要几百毫秒最多。假设树不会不断更新，这对于最终用户来说是完全可以接受的开销。

于 2014-09-17T14:54:49.277 回答