分段几何模型索引（PGM索引）是一种数据结构，它能够在包含数十亿条目的一维数组中实现快速查找、前驱查询、范围查询和更新操作，同时所需的空间仅为传统索引的极小一部分，并且能够提供相同的最坏情况查询时间保证。

官网 | 文档 | 论文 | 幻灯片 | Python封装库 | A³实验室

快速入门

这是一个仅包含头文件的库，无需安装。只需克隆仓库：

git clone https://github.com/gvinciguerra/PGM-index.git
cd PGM-index

然后将include/pgm目录复制到你的系统或项目的包含路径中。

examples/simple.cpp文件展示了如何使用PGM索引对一个随机整数向量进行索引和查询：

#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include "pgm/pgm_index.hpp"

int main() {
    // 生成一些随机数据
    std::vector<int> data(1000000);
    std::generate(data.begin(), data.end(), std::rand);
    data.push_back(42);
    std::sort(data.begin(), data.end());

    // 构建PGM索引
    const int epsilon = 128; // 空间-时间权衡参数
    pgm::PGMIndex<int, epsilon> index(data);

    // 查询PGM索引
    auto q = 42;
    auto range = index.search(q);
    auto lo = data.begin() + range.lo;
    auto hi = data.begin() + range.hi;
    std::cout << *std::lower_bound(lo, hi, q);

    return 0;
}

在Repl.it上运行并编辑此示例及其他示例。或者通过以下命令在本地运行：

g++ examples/simple.cpp -std=c++17 -I./include -o simple
./simple

类概述

除了上述示例中的pgm::PGMIndex类之外，本库还提供了以下类：

• pgm::DynamicPGMIndex支持插入和删除操作。
• pgm::MultidimensionalPGMIndex存储k维空间中的点，并支持正交范围查询。
• pgm::MappedPGMIndex将数据存储在磁盘上，并使用PGM索引来实现快速搜索操作。
• pgm::CompressedPGMIndex对段进行压缩，以减少索引占用的空间。
• pgm::OneLevelPGMIndex在段上使用二分查找，而不是递归结构。
• pgm::BucketingPGMIndex使用顶层查找表来加速对段的搜索。
• pgm::EliasFanoPGMIndex使用顶层简洁数据结构来加速对段的搜索。

完整的文档可在这里查阅。

编译测试和调优工具

克隆仓库后，使用以下命令构建项目：

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

测试程序将被放置在test/目录下。调优工具可执行文件将被放置在tuner/目录下。基准测试工具可执行文件将被放置在benchmark/目录下。

许可证

本项目采用Apache License 2.0许可协议。

如果您使用了该库，请务必附上官网链接，并引用以下论文：

Paolo Ferragina 和 Giorgio Vinciguerra. PGM索引：一种具有可证明最坏情况界线的全动态压缩学习索引。PVLDB, 13(8): 1162-1175, 2020.

@article{Ferragina:2020pgm,
  Author = {Paolo Ferragina and Giorgio Vinciguerra},
  Title = {The {PGM-index}: a fully-dynamic compressed learned index with provable worst-case bounds},
  Year = {2020},
  Volume = {13},
  Number = {8},
  Pages = {1162--1175},
  Doi = {10.14778/3389133.3389135},
  Url = {https://pgm.di.unipi.it},
  Issn = {2150-8097},
  Journal = {{PVLDB}}}

PGM-index 快速上手指南

PGM-index（分段几何模型索引）是一种高效的数据结构，能够在占用极小空间的同时，为数十亿级数据提供快速的查找、前驱查询、范围搜索及更新操作，并保证最坏情况下的查询时间性能。

环境准备

• 操作系统：支持 Linux、macOS 或 Windows (需配备兼容的 C++ 编译器)。
• 编译器：需要支持 C++17 标准的编译器（如 GCC 7+、Clang 5+ 或 MSVC 2019+）。
• 构建工具（仅编译测试或示例时需要）：cmake 和 make。
• 依赖库：无第三方运行时依赖。这是一个 Header-only（仅头文件）库，无需安装二进制包。

国内加速提示：如果克隆 GitHub 仓库速度较慢，可使用国内镜像源（如 Gitee 镜像，若有）或通过代理加速。若无特定镜像，标准克隆命令如下。

安装步骤

由于 PGM-index 是纯头文件库，无需执行复杂的安装脚本，只需将头文件复制到项目中即可。

1. 克隆仓库

   git clone https://github.com/gvinciguerra/PGM-index.git
   cd PGM-index
   

2. 配置头文件路径 将 include/pgm 目录复制到你项目的包含路径（include path）中，或者在编译时通过 -I 参数指定该目录。

   示例（复制到项目本地）：

   cp -r include/pgm /your/project/path/include/
   

3. （可选）编译官方示例 如果你想运行官方提供的测试或示例程序，需要构建项目：

   cmake . -DCMAKE_BUILD_TYPE=Release
   make -j8
   

   编译完成后，可执行文件将位于 test/、tuner/ 和 benchmark/ 目录中。

基本使用

以下是最简单的使用示例，展示如何构建索引并查询数据。

1. 创建一个 C++ 源文件（例如 simple.cpp），填入以下代码：

#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include "pgm/pgm_index.hpp"

int main() {
    // 生成一些随机数据
    std::vector<int> data(1000000);
    std::generate(data.begin(), data.end(), std::rand);
    data.push_back(42);
    std::sort(data.begin(), data.end());

    // 构建 PGM-index
    // epsilon 是空间与时间的权衡参数，值越大空间越小但查询可能稍慢
    const int epsilon = 128; 
    pgm::PGMIndex<int, epsilon> index(data);

    // 查询 PGM-index
    auto q = 42;
    auto range = index.search(q);
    
    // 获取搜索范围的迭代器
    auto lo = data.begin() + range.lo;
    auto hi = data.begin() + range.hi;
    
    // 在缩小后的范围内进行精确查找
    std::cout << *std::lower_bound(lo, hi, q) << std::endl;

    return 0;
}

2. 编译并运行 确保指定了 C++17 标准并包含了头文件目录：

   g++ simple.cpp -std=c++17 -I./include -o simple
   ./simple
   

其他可用类简介

除了基础的 pgm::PGMIndex，库还提供了以下变体以满足不同需求：

• pgm::DynamicPGMIndex：支持数据的动态插入和删除。
• pgm::MultidimensionalPGMIndex：支持 k 维数据的正交范围查询。
• pgm::MappedPGMIndex：支持磁盘存储数据的高效搜索。
• pgm::CompressedPGMIndex：进一步压缩段以减少空间占用。
• pgm::OneLevelPGMIndex、pgm::BucketingPGMIndex、pgm::EliasFanoPGMIndex：针对不同搜索优化策略的变体。