索引是一种用于加速数据查询的技术，在数据库中，索引通常基于表中的一列或多列的值创建，在索引中记录原始数据的存储位置，查询时通过索引能够快速定位数据。

使用索引也有代价，索引本身需要占用存储空间。同时，对表进行插入、更新或删除操作时，为了保证索引和数据的一致性，索引也需要更新，这会带来一定的性能开销。因此，在使用数据库时，需要权衡索引带来的查询性能提升和索引本身的开销。

BTREE索引具有稳定的查询性能，在插入和删除操作上也有不错的性能表现。这些特性使得BTREE索引成为了一种通用、可靠且高效的索引类型，很多主流关系型数据库的默认索引类型就是BTREE索引，MogDB 中默认的索引类型也是BTREE索引。

如果索引列上的值不具有唯一性，对应的索引称为非唯一索引。非唯一索引中如果有非常多的重复键，索引的存储空间占用和查询效率也受到影响。BTREE索引压缩技术（MogDB 产品从3.1版本引入），旨在减少索引中重复键的存储空间占用，降低存储成本。同时，经过压缩的索引空间占用减小，可以将更多的索引数据缓存在内存中，减少查询流程中索引的磁盘IO，提升查询性能。

Oracle索引压缩技术在9i版本(9.0.1.0, 2001/12/03, Oracle Real Application Clusters (RAC), Oracle XML DB)引入，旨在减小索引占用的存储空间、提高索引读取性能、降低I/O开销。Oracle 提供了多种索引压缩技术，其中最常见的是基于键的索引压缩(Key Compression)和基于前缀的索引压缩(Prefix Compression)。Oracle 的普通索引结构是B+树索引的变种B*树索引（branch节点之间存在关联关系，类似于叶子节点）。

• Advanced Index Compression is part of Advanced Compression Option in 12.1.0.2 and aims to automate index compression;高级索引压缩特性在12.1.0.2版本引入，主要改进是不用手动指定压缩prefix的范围；

• grouping piece对应prefix前缀，unique piece对应suffix后缀，如果键值不能提供unique piece，将会使用rowid来唯一标识；

• 只有B-Tree索引的叶子节点能被压缩，非叶子节点不能被压缩；

• 索引压缩是在单个block中完成，不能跨blocks进行索引压缩；

• grouping piece (prefix)和unique piece (suffix)存储在一起（相同的prefix在一个block中只存储一次，在解压缩流程中类似查表+拼接）。

DB2 数据库在9.7版本提出了索引压缩技术，DB2 的索引结构是B+树索引，索引执行压缩的时机是使用CPU的空闲周期或者是CPU在等待I/O时的周期对索引数据进行压缩、解压缩，具体压缩方案包含如下几点关键内容:

• 压缩数据存储: 磁盘和内存中索引page数据存储格式一致（都是压缩的）；

• 压缩算法选择对象: 由database manager选择（根据索引类型，索引存储的数据），非用户指定；

• 压缩算法适用场景: 对于1)存在大量重复key的场景采用RID-list delta压缩，对于2)存在index key之间较高相似度（单列中partial内容存在重复，或者multi colunm中其中几列存在重复，也可以是multi colunm中跨列存在重复度）场景采用前缀key压缩算法。

RocksDB 是一个以LSM-tree为存储结构的存储引擎，典型的KV存储系统，和上面讲到的商业数据库存储方式有区别，但是也有类似的索引结构存在，下面使用工具解析数据对索引数据的压缩的关键技术点分析如下:

图二

使用sst dump工具将磁盘上的sst文件解析出来，内容如上面的图，示意index block存放用来索引data block的key值的方式。

方式1：图中（如图一）的第一个index block索引的data block偏移地址找到对应的data block（如图二），可以看到index block的key和data block的起始key差异还是比较大，是采用了snappy压缩算法，也就是对index block中存放的key进行snappy压缩处理。

方式2：关闭snappy压缩，如果1号data block的结束key和2号data block的起始key如果有公共前缀，则索引2号data block的index block 会保存这个公共前缀key作为自己的index key，说明index block中采用2个相邻data block的key进行前缀压缩方式的存储方式存放key值（如图三）。

MogDB 中BTREE索引的具体实现是B-link tree结构，索引存储和数据一样，是采用堆表形式。索引中key存储在tuple元组中，索引中ctid指针指向数据。

非唯一索引中可能存在大量重复的key值，这部分数据(deduplicate data)占用大量存储空间，同时会影响索引的插入和查找效率。通过BTREE索引压缩计数，不仅可以减少这部分索引数据的空间占用问题，还能够一定程度提升索引的性能。

MogDB 数据库BTREE LAYOUT示意图

MogDB BTREE索引压缩方案的主要优化点:

• 合并索引页内的重复索引key

  同一个索引页内，如果索引key有重复，合并存储这些索引tuple。合并后的索引tuple 共用一个索引key，原来的每索引tuple ctid以列表的形式存储在合并后的索引 tuple 中。

• 压缩索引叶子节点

  对BTREE叶子节点(Leaf Node)进行压缩，根据索引key（单列/多列）的数据类型判断是否进行压缩处理。

• 优化BTREE分裂策略

  当索引页存在压缩与非压缩 tuple 交替的情况，原有方案中分裂策略，不能很好地找出分裂点。本方案对分裂策略进行了优化，且能够兼容原有方案，能根据页面数据占用情况选择合适的分裂点。

• 优化重复key插入

  对于重复key值的查找，原有方案每次插入时都需要使用二分查找获取按索引 key 有序的最小的插入位置，在存在大量重复 key 的情况下，改算法效率很低。优化后的方案针对重复索引 key 可以指定插入位置，从而避免或减少无效scan，提升性能。

• 日志并行回放

  记录索引压缩的批处理点BPP (Batch Process Point)，新增redo log支持索引并行回放。

• 兼容性

  MogDB 的索引压缩方案，从一开始就考虑到了兼容性问题。压缩后的BTREE索引，支持现有的插件和工具，能支持物理和逻辑复制，及导入导出等工具。

方案完成后，为验证实际效果，使用TPCC对索引的压缩效果进行了验证，测试中选择了具有代表性的三种数据类型：int8、text、timestamp 进行验证，并覆盖了单列和多列索引，最终对测试数据进行了总结。

TPCC模型测试数据结果

• 大部分测试场景下BTREE索引压缩效果比较明显，不同数据类型最终压缩后平均空间占用减少70%（压缩率2x以上）；

• 相同内存配置下，使用索引进行大数据量范围查找及普通点查，访问时延降低20%。