python - pytables File.get_node() 操作的时间复杂度

Question

pytables 文件操作的时间复杂度是多少get_node？

假设我查询

mynode = myfile.get_node(where='group0/group1/..../groupN', name ='mynode')

此操作如何随着 N 的父组数量扩展mynode？线性地，即 O(N)，或者更糟的 O(N*d)，其中 d 是我的 hdf5 节点树的平均分支因子，或者非常快的 O(1)，因为 pytables 内部保留了所有路径的某种字典？

非常感谢！

Answer 1

HDF5 将节点实现为 B 树，因此 get_node() 的时间复杂度为 O(log N) [1]。PyTables 不会在字典中对这些路径进行任何预加载以使其成为 O(1)。然而，一旦一个节点被加载，它就会被标记为“alive”并进入一个 alive_nodes 字典。因此，只要节点保留在内存中，后续访问就是 O(1)。所以这是一种懒惰的 O(1) 操作，你需要预先支付 O(log N) 的成本。

1. http://en.wikipedia.org/wiki/B-tree