存储和查询树的最有效方法是什么？

Question

我需要分析1 TB +的Web访问日志,特别是我需要分析与请求的URL和URL子分支(子分支)相关的统计信息.如果可能的话,我希望查询在数据的小子集上快速(例如1000万个请求).

例如,给定访问日志,请求以下URL:

/ocp/about_us.html
/ocp/security/ed-209/patches/urgent.html
/ocp/security/rc/
/ocp/food/
/weyland-yutani/products/

我想做的问题包括:

• 计算"低于"/ ocp的所有请求数.
• 与上面相同,但只计算/ ocp/security下子节点的请求
• 返回前5个最常请求的URL.
• 与上面相同,除了任意深度的组,

例如,对于上面的上一个查询,数据的深度2将返回:

2: /ocp/security/
1: /ocp/
1: /ocp/food/
1: /weyland-yutani/products/

我认为理想的方法可能是使用列DB并对URL进行标记,以便URL中的每个元素都有一列.但是,如果可能的话,我真的想找到一种方法来使用开源应用程序.HBase是一种可能性,但查询性能似乎太慢而无法用于实时查询(另外,我真的不想进行重新实现SQL的业务)

我知道有这种类型的分析有商业应用程序,但由于各种原因,我想自己实现这一点.

Answer 1

在投入太多时间在关系数据库之上设计分层数据结构之前,请考虑在 Bill Karwin 的优秀演示文稿SQL Anti-Patterns Strike Back中阅读"Naive Trees"部分(从幻灯片48开始).Bill概述了以下开发层次结构的方法:

1. 路径枚举(幻灯片55)
2. 嵌套(幻灯片58)
3. 关闭表(幻灯片68)