基于分层树的数组/矩阵索引，具有交叉边，这样的东西存在吗？

Question

尊敬的 StackOverflow 社区，您好，

我想知道数据结构文献中是否存在某种类型的基于分层树的数组/矩阵索引与交叉边缘，或者如果可能，这个想法使问题过于复杂。

准确描述我的想法：想象一个包含动物园动物总数的数组。其中每个数字代表特定动物的总数

[ 1, 51, 32, 4, 7, 23, ...]

可能有一个基于树的分层分类，允许人们识别每个数字的动物，甚至只是对类别进行求和。例如，这棵树可以是动物分类树：

- Kingdom
  - Phylum
    - Class
      - Order
        - Family
          - Genus
            - Species

在伪代码中我可以识别动物：

array[animalia.chordata.mammalia.primates.homindae.pan.chimpanzee]
> 5

或者我可以得到所有猿类甚至所有哺乳动物：

array[animalia.chordata.mammalia.primates.homindae]
> [5, 9, 3, 2]
sum(array[animalia.chordata.mammalia.primates.homindae])
> 19
sum(array[animalia.chordata.mammalia])
> 152

我想通过在数据结构中实现交叉边缘来进一步扩展这个概念，例如涉及食品的分类系统：

- Food Types
  - Fruits
    - Apple
    - Banana
  - Vegetables
    - Carrot
    - Spinach
  - Dairy
    - Milk
    - Cheese
  - Grains
    - Rice
    - Wheat
  - Beverages
    - Water
    - Soda
    - Milk

通过交叉边缘，某些食品可能会出现在多个类别中。例如，“牛奶”可以分为“乳制品”和“饮料”。考虑到此处的交叉边缘，多重索引并不是解决此索引结构的可行选择。因为多重索引必须是 MECE。

也许显而易见的答案是“否”，因为这些数据最好以表数据结构表示。因此，没有创建这样的概念。

但是，这种数据结构在某些会计实践中非常有用，在这些实践中，在不同帐户之间进行关系支付矩阵。也许这样做是因为它在 Excel 中更具视觉效果，并且以前从未使用代码完成过。然而，如果可以使用上述功能沿任一轴表示和切片索引，则它可能对分析有用。该数据的分析依赖于账户之间类似矩阵的支付结构。因此，以长表格格式包含数据将使分析变得更加困难。

我看到的主要问题：

1. 插入和删除是复杂且昂贵的操作
2. 聚合是复杂且昂贵的操作

主要问题

如果有人对可能存在的数据结构有任何了解，或者是否有表示此数据的最佳实践，我将不胜感激。也许解决方案是保留长表格式、过滤、分组和聚合，然后重新回到矩阵格式。

1. 这样的数据结构存在吗？
2. 如果不是，主要并发症是什么？
3. 构建这些数据的最佳方法是什么？

希望有任何见解。

Answer 1

这听起来像一个顺序统计树。它有一个额外的字段，描述当前节点下的节点数量。虽然更新需要空间和时间的开销，但总体运行时复杂性是相同的（但更容易创建不一致的树。）

通常，顺序静态树由B树或其他自平衡树组成，可以在

log(n)

时间内执行操作。 Python 模块 blist 使用顺序统计树来提高

list

性能，但我不知道这在您的特定情况下是否有用。

您具体描述的是具有明确固定结构的树，在这种情况下，

log(n)

保证不一定成立。而且，键（动物）都在底部，结构类似于B+树。您的第二个示例是“多对多”模型；通常有一个将食物映射到标签的中间结构，但这取决于人们需要从数据中获得什么。