xml数据管理技术(编辑修改稿)

xml数据管理技术(编辑修改稿)内容摘要：

1) (start, end, level) (2, ,2) 3(4, ,2) (5, ,3) 6 (7, ,3) 89 (10, ,2) 11(12, ,2) 17 (13, ,3) 14 (15, ,3) 16 18 1 18 5 6 7 8 a d (1, 18, 1) (5, 6, 3) (7, 8, 3) 2020/10/8 24/65 编码方案 为什么使用编码 已有的解决方案 区间编码 路径编码 a1 b1 b2 b3 c1 d1 d2 e1 f1 a d Query Document a d 1 1 2020/10/8 25/65 编码方案 为什么使用编码 已有的解决方案 实际问题 文档更新 插入叶子节点 插入非叶子节点 节点编码需要更新 a d Query Document a1 b1 b2 b3 c1 d1 d2 e1 f1 (1, ,1) (2, ,2) 3(4, ,2) (5, ,3) 6 (7, ,3) 89 (10, ,2) 11(12, ,2) 17 (13, ,3) 14 (15, ,3) 16 18g a1 b1 b2 b3 c1 d1 d2 e1 f1 1 g g g g 2020/10/8 26/65 编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 无法避免重新编码 a d Query Document a1 b1 b2 b3 c1 d1 d2 e1 f1 (10, ,1) (20, ,2) 30 (40, ,2) (50, ,3) 60 (70, ,3) 80 90 (100, ,2) 110 (120, ,2) 170 (130, ,3) 140 (150, ,3) 160 180 2020/10/8 27/65 编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 无法避免重新编码 a d Query Document a1 b1 b2 b3 c1 d1 d2 e1 f1 (1, ,1) (2, ,2) 3(4, ,2) (5, ,3) 6 (7, ,3) 89 (10, ,2) 11(12, ,2) 17 (13, ,3) 14 (15, ,3) 16 18g1 g2 (, , 3) (101, 110, 3) (111, 1000, 3) (, , 3) 2020/10/8 28/65 编码方案 为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 ORDPATH 代价高 a1 b1 b2 b4 c1 d1 d2 e1 f1 a1 b1 b4 c1 e1 f1 1 b2 d1 d2 b2 b3 2020/10/8 29/65 编码方案  为什么使用编码  已有的解决方案  已有更新方法  空间预留  浮点数编码  路径编码  素数编码  可避免更新编码  N值计算代价高 xilabelNilabelN ni )(mod])(,0[1a1 b2 c1 d1 d2 e1 f1 1 2 3 5 7 11 13 1 2=2*1 6=3*2 10=5*2 7=7*1 77=11*7 91=13*7 d1 17 170=17*10 1153210  NN1=1523 N2=6 N1=1139 N2=72 72 N N N N N 3 4 5 N N N N N 2020/10/8 30/65 编码方案  为什么使用编码  已有的解决方案  已有更新方法  空间预留  浮点数编码  路径编码  素数编码  二进制位串 将整数用二进制字符串表示 a1 b1 b2 b3 c1 d1 d2 e1 f1 (1, ,1) (2, ,2) 3(4, ,2) (5, ,3) 6 (7, ,3) 89 (10, ,2) 11(12, ,2) 17 (13, ,3) 14 (15, ,3) 16 18将插入整数变为插入字符串 0 size=0 19 size=0 (01, 01001, 001) (0101, 011, 001) g (010011, 0100111, 001) 2020/10/8 31/65 编码方案  为什么使用编码  已有的解决方案  已有更新方法  空间预留  浮点数编码  路径编码  素数编码  位串编码  向量编码 将整数用向量表示 a1 b1 b2 b3 c1 d1 d2 e1 f1 (1, ,1) (2, ,2) 3(4, ,2) (5, ,3) 6 (7, ,3) 89 (10, ,2) 11(12, ,2) 17 (13, ,3) 14 (15, ,3) 16 18将插入整数变为插入向量 2020/10/8 32/65 编码方案  为什么使用编码  已有的解决方案  已有更新方法  空间预留  浮点数编码  路径编码  素数编码  位串编码  向量编码 a1 b1 b2 b3 c1 d1 d2 e1 f1 (1, ,1) (2, ,2) 3(4, ,2) (5, ,3) 6 (7。