Skip to content
This repository has been archived by the owner on Jan 18, 2020. It is now read-only.

索引

Jump to bottom
Zhen Chen edited this page Jan 10, 2020 · 1 revision

Table of Contents

索引（Index）

  • 定义
索引（Index）是加快查找（Search）功用的数据结构（Data Structure）。
  • 用于索引的数据结构
用于索引功能的数据结构有哈希表（Hash Table）、树（Tree）、整数数组/链表（Integer Array/Linked List）和位图（Bitmap）。
  • 索引的应用：分布式系统、数据库与数据系统、信息检索等
  • 教科书：
索引结构的设计可参考《算法与数据结构》教科书中的搜索（Search）的章节。
  1. Thomas H. Cormen, Introduction to algorithms, third edition, MIT press, 2009.
  2. Eva Tardos and Jon Kleinberg, Algorithm Design, Pearson, 2006.
  3. Tim Roughgarden, Algorithms Illuminated.

索引的形式

索引的数据结构包括哈希表（Hash Table）、树（Tree）、整数数组/链表（Integer Array/ Linked List）和位图（Bitmap）。

哈希表（Hash Table）

  1. B. H. Bloom,Space/time trade-offs in hash coding with allowable errors, Commun. ACM, Volume 13 Issue 7, Pages 422-426, July 1970.
  2. Crainiceanu, Adina, and Daniel Lemire. "Bloofi: Multidimensional Bloom Filters." Information Systems 54 (2015): 311-324.
  3. Chazelle, Bernard, et al. "The Bloomier filter: an efficient data structure for static support lookup tables." SODA, 2004.

树（Tree）

平衡树 B-Tree

  1. Guttman, Antonin. R-trees: a dynamic index structure for spatial searching. Vol. 14, no. 2. ACM, 1984.
  2. Sellis, Timos, Nick Roussopoulos, and Christos Faloutsos. "The R+-Tree: A Dynamic Index for Multi-Dimensional Objects." VLDB, 1987.

整数数组/链表（Integer Array/List）

Verbatim Integer List 带来的空间开销，人们发明了Integer List Compression机制，尤其是compressing 32-bit unsigned integers。

  • BP128 (Binary packing ) / SIMDBP128 /
  • FastPFor
  • FOR (Frame of reference) / PFOR (Patched Frame of reference) / PFOR Delta (PFOR on deltas) / NewPforDelta /SIMDPforDelta
  • Simple16 / Simple8b
  • VByte（or VB ） / VarIntGB（or GroupVB ） / StreamVByte /MaskedVByte SIMD-accelerated VByte / MaskedVByte
  • PEF (Partitioned Elias-Fano) Partitioned Elias-Fano
  • Data Structures for Inverted Indexes (ds2i)
    • 研究论文：
  1. Daniel Lemire and Christoph Rupp. Upscaledb: Efficient Integer-Key Compression in a Key-Value Store using SIMD Instructions. Information Systems, 2017.
  2. D. Lemire, L. Boytsov, N. Kurz, SIMD compression and the intersection of sorted integers, Softw. Pract. Exp. 46 (6) (2016) 723–749.
  3. Jeff Plaisance, Nathan Kurz, and Daniel Lemire. "Vectorized vbyte decoding." CoRR, abs/1503.07387, 2015.
  4. Jeff Plaisance, Nathan Kurz, Daniel Lemire, Vectorized VByte Decoding, International Symposium on Web Algorithms 2015, 2015.
  5. D. Lemire and L. Boytsov. Decoding billions of integers per second through vectorization. Softw. Pract. Exp. 45 (1) (2015) 1–29.
  6. Inoue, Hiroshi, Moriyoshi Ohara, and Kenjiro Taura, Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions, VLDB 2014.
  7. Kane, Andrew, and Frank Wm Tompa, Skewed Partial Bitvectors for List Intersection, SIGIR 2014.
  8. Schlegel, Benjamin, Thomas Willhalm, and Wolfgang Lehner. Fast Sorted-Set Intersection using SIMD Instructions, ADMS 2011.
  9. Zukowski, Marcin, Sandor Heman, Niels Nes, and Peter Boncz. "Super-scalar RAM-CPU cache compression." ICDE 2006.

位图（Bitmap）

应用环境：特别适合作为数据管理中的列式存储（Column-oriented or Columnar ）的索引和信息检索中的反向索引的数据结构。

Bit array

A bit array (also known as bit map , bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure.

https://en.wikipedia.org/wiki/Bit_array

  • Population / Hamming weight
  • Find first set (ffs) or Find first one
  • Inversion
    • 研究论文：
  1. Matthias Vallentin, Vern Paxson, and Robin Sommer. "VAST: a unified platform for interactive network forensics." NSDI 2016.
  2. Gonzalo Navarro and Eliana Providel. “Fast, Small, Simple Rank/Select on Bitmaps.” SEA 2013.

位图压缩

Verbatim Bitmap 带来的空间开销，尤其是bitmap很稀疏的情况下。为此，人们发明了Bitmap Compression机制。不仅可以降低空间开销，而且可以显著加快运算速度。

在1995年，甲骨文公司（oracle）的G. Antoshekov展示了一种新的针对位图索引的压缩算法Byte-Aligned Bitmap Compression（BBC）。

在此之后，WAH (Word Aligned Hybrid compression), PLWAH (Position list word aligned hybrid), COMPAX (COMPressed Adaptive indeX) 等多种索引压缩方法被提出，在国际上被认可并在数据库索引编码中被广泛应用。

目前，已有相关运营软件产生，如Spark, Fastbit , Druid 等平台。

    • 可运算的位图压缩方法
  • BBC (Byte-aligned Bitmap Compression)
  • WAH (Word Aligned Hybrid)
  • PLWAH (Position List Word-Aligned Hybrid)
  • EWAH (Enhanced Word-Aligned Hybrid )
  • CONCISE (COmpressed N Composable Integer SEt)
  • PWAH (Partitioned Word-Aligned Hybrid)
  • COMPAX (COMPressed Adaptive indeX )
  • SBH （Super byte-aligned hybrid）
    • 与反向索引的比较
[1] Wang, Jianguo, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. "An Experimental Study of Bitmap Compression vs. Inverted List Compression." ACM SIGMOD 2017.
    • 研究论文
[1] Antoshekov G. Byte-aligned bitmap compression. Proc of the Conf on Data Compression. Piscataway, NJ: IEEE, 1994: 363- 098, 1994.

[2] Wu, Kesheng, Ekow J. Otoo, and Arie Shoshani. "Compressing bitmap indexes for faster search operations." In Scientific and Statistical Database Management(SSDBM), 2002.

[3] Wu, K., Otoo, E. J., and Shoshani, A. Optimizing bitmap indices with efficient compression. ACM Transactions on Database Systems (TODS), 31(1), 1-38, 2006.

[4] Stabno, Michał, and Robert Wrembel. "RLH: Bitmap compression technique based on run-length and Huffman encoding." Information Systems 34, no. 4, pp.400-414, 2009.

[5] F. Fusco, M. P. Stoecklin, and M. Vlachos, “Net-fli: on-the-fly compression, archiving and indexing of streaming network traffic,” Proceedings of the VLDB Endowment, vol. 3, no. 1-2, pp. 1382–1393, 2010.

[6] F. Deli`ege, T. B. Pedersen. Position list word aligned hybrid: optimizing space and performance for compressed bitmaps. EDBT 2010.

[7] F. Corrales, D. Chiu, and J. Sawin, “Variable Length Compression for Bitmap Indexes,” DEXA 2011.

[8] D. Lemire et al., “Sorting improves word-aligned bitmap indexes,” Data & Knowledge Engineering, 69(1), pp.3-28, 2010.

[9] S. J. van Schaik et al., “A memory efficient reachability data structure through bit vector compression,” SIGMOD, pp.913-924, 2011.

[10] S. Chambi, D. Lemire, O. Kaser, and R. Godin, “Better bitmap performance with roaring bitmaps,” Software: Practice and Experience, 2015.

[11] A. Schmidt, D. Kimmig, and M. Beine, "DFWAH: A Proposal of a New Compression Scheme of Medium-Sparse Bitmaps," DBKDA 2011.

[12] R. Slechta, J. Sawin, B. McCamish, D. Chiu and G. Canahuate, A tunable compression framework for bitmap indices, ICDE 2014.

[13] Kim, Sangchul, Junhee Lee, Srinivasa Rao Satti, and Bongki Moon. "SBH: Super byte-aligned hybrid bitmap compression." Information Systems 62 (2016): 155-168.

    • 研究专利
[1] BBC, Byte aligned data compression, DEC/Oracle, http://www.google.com/patents/US5363098.

[2] WAH, Word aligned bitmap compression method, data structure, and apparatus, UC Berkeley, http://www.google.com/patents/US6831575.

[3] COMPAX, Network analysis, IBM, http://www.google.com/patents/US20120054160.

[4] PLWAH, Algorhyme, http://www.google.com/patents/US9236881.

位图索引应用

2014年12月俄勒冈州立大学的Ben McCamish等人提出了一个由数据驱动的能源系统实时监测与可视化的框架，将传感器采集的数据用位图存储，并使用WAH算法压缩，从而减小了数据存储空间，提高了查询速度。

  1. McCamish, Ben, Rich Meier, Jordan Landford, Robert B. Bass, David Chiu, and Eduardo Cotilla-Sanchez. "A backend framework for the efficient management of power system measurements." Electric Power Systems Research 140 (2016): 797-805.

Roaring

  • Roaring Bitmap
Roaring Bitmap 是一种为索引（Indexes）的运算(与，或，非)而优化的混合数据结构。

Roaring 数据结构内部采用位图Bitmap，整数数组Arrays和游程编码Runs的表示形式，三种表示形式是平等的。当数据以其中某种表示结构的表示时，整体空间为最优，Roaring则采用该表示结构。也就是说，Roaring采用空间最优化的数据表示结构。

Roaring表示的索引之间可以进行高效的运算。运算时，无非也是位图Bitmap，整数数组Arrays和游程编码Runs这三种结构之间的运算。

所有，Roaring是兼顾空间与时间效率的一种有效的索引结构。

Roaring网址：http://roaringbitmap.org/

Roaring的Java实现 Java-Roaring

Roaring的C/C++实现 CRoaring

  • Roaring 研究论文：
    • Roaring Hybrid
  1. Lemire, Daniel, Gregory Ssi‐Yan‐Kai, and Owen Kaser. "Consistently faster and smaller compressed bitmaps with Roaring." Software: Practice and Experience 46.11 (2016): 1547-1569.
    • Native Roaring
  1. Samy Chambi, Daniel Lemire, Owen Kaser, and Robert Godin. "Better bitmap performance with Roaring bitmaps." Software: practice and experience, 2015.

混合结构（Hybrid）

融合几种独立结构的混合结构。

Poptrie

本身设计是为了IP地址的压缩存储与快速查询，但是通过合适扩展其思想也可以被用于更广范围的数据存储。

Poptrie主要通过改进trie的思想来提升效率。Trie是通过树形结构来存储数据，主要利用数据之间前缀的重叠来提高存储效率。

其大体实现方法是先将数据分块，每一块对应树的一层，而每一层的节点的最大孩子节点数即为该块数据的可能至的数目，即每一个位置的孩子对应一块数据的一种取值。通过这种方法我们可以将一些数据构造成一棵树。这种方式当数据之间前缀重叠率高时，效果出色，而重叠率低时，可能反而会浪费空间。

Poptire改变之前每个位置都需要记录一个地址的问题，转而通过一个0/1记录该位置的孩子节点性质，同时在维护两个基地址，分别对应孩子节点为叶子节点和中间节点时的首地址，也就是说通过两个地址和一些0/1值代替原先的许多地址。为了能够读取，规定每个节点的所有叶子节点和所有中间节点都是连续存储的，也就是说可以通过指针的移动找到所有孩子节点的地址。在读取时，需要求出当前值对应的位置之前有多少叶子节点,而这可以通过记录的0/1值完成。同时为了进一步提升效率，Poptrie还将相同的叶子节点合并，同时再辅以一些0/1值来记录合并情况。

此外，Poptrie还考虑到在数据重叠性差时Trie树的糟糕反应，决定允许树的边跨越多层，即可以跳过一些层，在极端情况下，即只有一个数据时，可以由根指向表示该数据的叶子节点，避免在中间各层浪费空间。

在相关的论文中，研究人员已经验证在一些情况下，Poptrie处理IP地址数据是较为高效的。

  1. Hirochika Asai, Ohara Y, Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup, sigcomm 2014.
    • 研究论文：
  1. Athanassoulis, Manos, and Anastasia Ailamaki. "BF-tree: approximate tree indexing." Proceedings of the VLDB Endowment 7, no. 14 (2014): 1881-1892.
  2. Alex Galakatos, Michael Markovitch. Carsten Binnig, Rodrigo Fonseca, Tim Kraska, A-tree: A bounded approximate index structure, arxiv, https://arxiv.org/abs/1801.10207.
  3. Lakshminarasimhan, Sriram, et al. "Scalable in situ scientific data encoding for analytical query processing." HPDC 2013.
    • 研究论文：
  1. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi. Hybrid Compression of Bitvectors for the FM-Index. In Proc. 2014 Data Compression Conference (DCC 2014), pp. 302-311, 2014.
  2. Gagie, Travis, Gonzalo Navarro, and Simon J. Puglisi. 2012. “New algorithms on wavelet trees and applications to information retrieval.” Theoretical Computer Science 426: 25–41.

其它结构（Others）

位图索引时会用到变长度码来压缩数据，然而通常的压缩算法在解压的时候必须全部展开才能查询某一个特定的位置，因此使用起来效率低下。

西班牙拉科鲁尼亚大学的Nieves R. Brisaboa1,et al提出运用一种符号重排的技巧，我们可以直接访问变长度码的第i个数据。这种压缩要求保持可查询性，也就是能够既保证压缩率又保证可索引性。从而实现快速处理位图索引的取样的同时，做到尽量节省存储空间。

  1. Brisaboa, Nieves R., Susana Ladra, and Gonzalo Navarro. "Directly addressable variable-length codes." In International Symposium on String Processing and Information Retrieval, pp. 122-130. Springer Berlin Heidelberg, 2009.

SDSL - Succinct Data Structure Library

索引应用（数据管理）

大数据系统的数据管理，采用位图索引、树索引等。

  • 树索引在数据库中应用广泛。
  • 位图索引的应用
位图索引在数据库、版本控制系统都有应用。

Git软件的对象计数问题

对象计数问题（counting objects）是git软件进行git clone时，需要实时计算出需要克隆的对象总数。

Git的对象（object）就是文件，包括快照对象（Commit），目录对象（Directory）和文件对象（File）。

"对象计数"就是清点各种commit、目录、文件等。git clone和git fetch操作都需要清点对象，因为需要知道，到底下载哪些对象文件。

对象计数的原始算法如下。

  1. 列出本地所有分支最新的一个commit
  2. 列出远程所有分支最新的一个commit
  3. 两者进行比较，只要有不同，就意味着分支发生变动
  4. 每一个发生变动的commit，都清点其中具体变动的子目录和文件
  5. 追溯到当前commit的父节点，重复第四步，直至本地与远程的历史一致为止
  6. 加总所有需要变动的对象

对象计数的位图索引方法

Git软件为为每一个commit生成一个二进制值，即Bitmap索引。

打开本地目录：.git/objects/pack/，其中是一个索引文件和一个数据文件，它们就是Bitmap。这两个文件索引了当前代码库的所有对象，然后使用一个二进制值代表这些对象。有多少个对象，这个二进制值就有多少位。它的第n位，就代表数据文件里面的第n个对象。

每个commit都会有一个对应的二进制值，表示当前快照包含的所有对象。这些对象对应的二进制位都为1，其他二进制位都为0。

采用位图索引的优点是：

  1. 不用读取commit对象，只要读取这个二进制值，就会知道当前commit包含了哪些节点。
  2. 两个二进制值只要做一次XOR运算，就会知道哪些位（即哪些对象）发生了变动。
  3. 新的对象总是添加到现有二进制位的后面，所以只要读取多出来的那些位，就知道当前commit比上一次commit多出了哪些对象。
因为采用位图索引，"对象计数"就变成了位图的二进制值的比较运算和计数运算，因此速度极快。

参考链接

https://githubengineering.com/counting-objects/

http://www.ruanyifeng.com/blog/2015/09/git-bitmap.html

https://github.com/gitster/git/commit/fff4275

https://github.com/gitster/git/blob/master/Documentation/technical/bitmap-format.txt

索引应用（信息检索）

搜索引擎（Search Engine）是一种典型的信息检索的大数据系统，是实现信息检索（Information Retrieval）的软件。

经典的搜索引擎主要是针对爬取的网页文本的检索。 一个网页文本或文档，是由许多的单词组成的。其中每个单词可以在同一个文档中重复出现很多次，同一个单词也可以出现在不同的文档中。

反向索引（Inverted Index）的原理

为了实现快速的搜索响应，搜索引擎采用反向索引（Inverted Index）的数据结构。反向索引在信息检索中发挥重要作用。这里介绍一下前向索引（forward index）和反向索引（Inverted Index）的概念。

前向索引(forward index)：从文档角度看其中的单词，表示每个文档（用文档ID标识）都含有哪些单词，以及每个单词出现了多少次（词频）及其出现位置（相对于文档首部的偏移量）。

反向索引(inverted index 或inverted files)：从单词角度看文档，标识每个单词分别在那些文档中出现(文档ID)，以及在各自的文档中每个单词分别出现了多少次（词频）及其出现位置（相对于该文档首部的偏移量）。

直观表示：

前向索引（一对多映射）：文档 ---> 单词 




反向索引（一对多映射）：单词 ---> 文档



前向索引，又称为正排索引；反向索引，又称为倒排索引。但是正排和倒排索引的称谓，会造成误解。





反向索引（Inverted Index）的实现






反向索引的功能是将关键字（keyword）映射到文档（document）。



在反向索引中，每个关键词对应一个反向链表（Inverted List），记录了该关键词出现的所有文档的编号。



反向索引在实际实现中，可以采用位图（Bitmap）与整数数组/链表（Integer Array/List）两种结构形式。









    • 研究论文：
  1. Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, Optimal Space-Time Tradeoffs for Inverted Indexes, ACM WSDM 2015.



反向索引（Inverted Index）的运算






反向索引上的最重要的运算是集合交（Conjunction），并（Disjunction）和非（Negation）。



反向索引上的交，并和非运算，对应的整数链表的实现，其操作是Intersection/Unions操作，对应位图的实现，其操作运算则是比特AND，OR，NOT操作。









    • 研究论文：
  1. Culpepper, J. Shane, and Alistair Moffat. "Efficient set intersection for inverted indexing." ACM Transactions on Information Systems (TOIS), 2010.



反向索引的参考实现






Lucene



Whoosh



OpenSearchServer





软件代码库








  • pyRoaringBitMap 

https://github.com/Ezibenroc/PyRoaringBitMap

 from pyroaring import BitMap

 bm1 = BitMap()
 bm1.add(3)
 bm1.add(18)
 bm2 = BitMap([3, 27, 42])

 print("bm1       = %s" % bm1)
 print("bm2       = %s" % bm2)
 print("bm1 & bm2 = %s" % (bm1&bm2))
 print("bm1 | bm2 = %s" % (bm1|bm2))






大数据系统-科研






SaturnLab长期从事大数据索引的研究工作，详细内容可参见大数据系统-科研。






参考文献






大数据索引技术 - B+ tree vs LSM tree, https://www.cnblogs.com/fxjwind/archive/2012/06/09/2543357.html 



MySQL索引背后的数据结构及算法原理, http://www.codinglabs.org/html/theory-of-mysql-index.html

              


              

                

                  

                    

清华大学iCenter人工智能系统实验室

                  

                

              

          



  
          

            

              

                

                  

                    
BDMI-2019 Autumn AI lab


                  

                

              


            
Clone this wiki locally