标题：PH-tree，一个空间高效的存储结构和多维索引

ABSTRACT

• PH-tree：全称PATRICIA-hypercube-tree，是把之前一种叫做PATRICIA-trie的二叉树和超立方体合并起来设计的。
• 特色：空间高效。PH-tree是一个内存索引，带有一定的压缩性质。用这个索引存数据，有时甚至比存原数据还要小。

1. INTRODUCTION

• 搜索高效：与维数无关
• 结构与构造顺序无关
• 更新高效：最多涉及两个节点

3. THE PH-TREE

PH-tree将高维数据全部二进制表示，基于trie树的前缀和四叉树的多扇出。优点如下：

• 四叉结构，同时考虑所有维度。
  • 使得访问与维度存储的顺序无关。
  • 使得节点数量减少。
  • 使得树高度与维度无关。
• 因为高度有限制，所以即使PH-tree不是平衡树，也不需要单独为它的平衡性考虑，因为插入，更新最多和两个节点相关。
• PH-tree节点数目虽多，但是把每个节点的size，或者说节点内空间利用率提升了，用更少的空间存储同样多的信息。当然带一些性能代价。
• 超立方体寻址很快，一次数组查询就可以完成k维分割；二叉树就要路由k个节点。

3.1 The 1D-PH-Tree

先从存放1维数据开始讲起。假设每个1维数据有4个bit来表示，1维的PH-tree就类似一个trie树，存放这些bit串。如下图。

• 这个PH-tree高度最高就是4，每一维数据的bit宽度。

  
  image.png

3.2 The kD-PH-Tree

当存放k维数据时，第一层使用各个维度的第一个bit，依次类推。每个节点称一个超立方体，节点中的数字称地址。

image.png

3.3 Floating Point Values

浮点数都是IEEE754存储的，二进制码和十进制的大小没什么关系。因此本文转换了存储模式，使得二进制码的顺序和十进制顺序一致。

【后续是复杂度分析和实验，有空补充】