1.跳跃表(skipList)
什么是skiplist
- 跳跃表（skiplist）是一种随机化的数据， 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出， 跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。
图示
用途：
- Redis
2.哈希索引（Hash Index）
什么是hash Index
- 基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
- 哈希索引可细分为静态哈希和动态哈希这两大类，
静态哈希
- 基于散列技术的文件组织使我们能够避免访问索引结构，同时也提供了一种构造索引的方法。在对散列的描述中，使用桶(bucket)来表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块，但也可能大于或者小于一个磁盘块。
- 散列索引将散列函数作用于搜索码以确定对应的桶， 然后将此搜索码以及对应的指针存入此桶(或溢出桶)中。
- 静态散列最大的缺点在于必须在实现系统时选择确定的散列函数。此后若被索引的文件变大或缩小，要想再改变散列函数就不容易了。因为散列函数 h 将搜索码值映射到桶地址的固定集合 B 上：
- 根据当前文件大小选择散列函数，这样的选择会使得性能随着数据库的增大而下降。换言之，初始时集合 B 太小，一个桶就会包含许多不同的搜索码值的记录，从而可能发生桶溢出。当文件变大时，性能就会受到影响。
- 根据将来某个时刻文件的预计大小选择散列函数。 尽管这样可以避免性能下降，但是初始时会造成相当大的空间浪费。
动态哈希
- 针对静态散列技术出现的问题，动态散列（dynamic hashing）技术允许散列函数动态改变，以适应数据库增大或缩小的需要
- 当数据库增大或缩小时，可扩充散列可以通过桶的分裂或合并来适应数据库大小的变化，这样可以保持空间的使用效率。此外，由于重组每次仅作用于一个桶，因此所带来的性能开销较低。
图示
3.ssTable
什么是ssTable
- SSTable文件是memtable 数据到一定阈值写入文件形成的，由于内存容量总是有限的，将一定量数据写入磁盘可以存放更多数据，所以leveldb相比redis能存放更多数据。既然数据持久化到磁盘，那么还有必然涉及到从磁盘中查询数据，从磁盘中查询数据与从内存中查询数据的效率是不一样的，所以SSTable 数据组织方式必然与众不同，因为必须要提高查询效率，不能给一个key就去遍历所有SSTable。因此本文的另一个目的就是学习SSTable 文件如何组织key-value，提高查询效率。为了提高内存中数据查询效率 我们学习了各种数据结构如红黑树，散列表，那么SSTable是学习如何提高文件查询数据效率的一个很好例子。
图示
4.LSM树(LSM Tree)
什么是LSM Tree
- LSM 树，即日志结构合并树（Log-Structured Merge-Tree）是Google BigTable 和 HBase 的基本存储算法，它是传统关系型数据库的 B+ 数的改进。算法的关注重心是 “如何在频繁的数据改动下保持系统读取速度的稳定性”，算法的核心在于尽量保证数据是顺序存储到磁盘上的，并且会有频繁地对数据进行整理，保证其顺序性。而顺序性就可以最大程度保证数据的读取性能稳定。
- 一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中，使用日志结构合并树（Log-structured Merge Tree，LSM Tree）来组织数据。
图示
5.B树(B tree)
什么是B tree
- B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
图示
6.倒排索引(inverted index)
什么是inverted index
- 倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。
图示
7.后缀树(Suffix tree)
什么是Suffix tree
- 后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner于1973年提出，既而由McCreight在1976年和Ukkonen在1992年和1995年加以改进完善。
图示
8.R树(R Tree)
什么是RM Tree
- R-tree是B-tree向多维空间发展的另一种形式，它将空间对象按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的 所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。每个结点所能拥有的子结点数目有上、下限，下限 保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页，当插入新的结点导致某结点要求的空间大于一个磁盘页时，该结点一分为二(分裂)。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。
