IndexingXMLData
来自 PostgreSQL wiki
跳转到导航跳转到搜索构想
PostgreSQL 中当前的索引方法并不符合 XML 规范。此 GSoC 项目基于 GiST 创建新索引（代码名为 FastX），该索引将遵循不同的 XML 数据处理方式。索引结构可能用于 Xquery 或 Xpath 2.0 支持，无需 LibXML，因为 LibXML 不支持该查询技术。但这是未来趋势，如今的实现对 XPath 使用 LibXML，因此可以从仅选择 XML 文档的子部分开始，然后由 LibXML 解析和查询。这样做的好处是，在执行 XPath 查询期间所需 CPU 和内存减少了。
详情
我的研究表明，已经发明了许多 XML 索引技术，比较这些技术本身就是一项非常困难的项目。可以在 [1] 中找到一些比较内容。2007 年，Nikolay Samokhvalov（PostgreSQL 黑客）提出了基于 ORDPATH 方法（在 SQL Server 中使用）的 XLABEL 索引技术，该技术使用切分 XML 文档来关联模型 [2]。
我的方法不同。我不使用切分技术，而是混合方法，这种方法基于由 XML 属性丰富的帕特里夏树。基本原理和 [3] 和 [4] 中定义的IndexFabric 相同。
算法说明
帕特里夏树
Trie 是一种字符串存储树，其中每个公共前缀都有一个节点。字符串存储在额外的叶节点中。帕特里夏树是压缩 Trie 的一种简单形式，它将具有单一子节点的节点与父节点合并。对于长键（一个节点的不常见后缀）更有效。
IndexFabric 基点
<?xml version="1.0" ?> <book> <title>survey</title> <chapter> <section>index</section> <section> <paragraph>by</paragraph> </section> </chapter> <chapter> <section>indeed</section> <section>data</section> </chapter> <appendix /> </book>
说明
- 文本搜索数据指南扩展
- 保留从根节点开始的所有标签路径
- 将带数据值的每个标签路径用字符串编码
- 使用高效的字符串索引存储它（帕特里夏树）
- 对元素执行关键词查询作为字符串搜索
- 不保留非终端节点的信息
- 使用带有元素代码的指示符表
Fabric 索引评估
- 标识符
- 每个文档一个
- 后代/祖先搜索
- 作为字符串搜索；不保留元素的顺序
- 关键词搜索
- 如果展开，则由帕特里夏树叶进行；否则由值索引进行
- 更新
- 插入是增量的
- 删除很复杂
- 索引大小（与文档一起存储的索引）
- 条目数：对于树，是线性的
- 条目大小：路径中元素的数量
FastX 更改使用两个单独的表，其中一个被命名为xnames，存储所有元素名称以及 XML 文档开头的偏移。第二个表是xattribs，其中包含所有元素的所有属性的完整名称。
联系方式
日程
- 截止到 5 月 25 日
- 研究现有索引技术，用于硕士论文
- 6 月 26 日到 6 月 16 日
- 使用 LibXML2 遍历方法（XMLReader、SAX）创建第一个模型
- 6 月 17 日到 6 月 22 日
- 硕士毕业论文答辩
- 6 月 23 日到 7 月 7 日
- 为元素实现索引，并准备进行中期评估。
- 在具有代表性的数据集种类上进行基准测试。
- 7 月 8 日到 8 月 16 日
- 在尽可能广泛的数据集上进行详细基准测试。
- 最终重构、测试和提交。
