倒排索引

数据结构分为词表和倒排表两部分。
词表：FST。类似于字典树（适合英文），共享前缀，内存消耗小； https://blog.csdn.net/njpjsoftdev/article/details/54015485
倒排表：文档号集合。数据压缩+有序链表+跳表 https://blog.csdn.net/hu948162999/article/details/79042439

空间索引

为什么要建立空间索引

空间索引的建立是因为人们对依据空间位置来进行查询的要求而产生的。举一个简单的例子，如何根据自己所在位置来查询附近100m的POI(point of interest)，直接计算位置与所有POI的距离，并保留距离小于100m的POI，这种方法耗时较长，运算的效率低下。

怎么建空间索引。

思想：将研究区域按一定规则用横竖线分为小的网格，记录每个网格所包含的地理对象。当用户进行空间查询时，首先计算查询对象所在的网格，然后查看落下哪个点，和他周边的索引，最后再计算每个块和点之间的距离。保留满足条件的距离

1、hash 网格索引

（1）索引实现：使用Hash数据结构实现，单位网格对应于HashMap中的一个桶，该网格关联的对象对应存储在相应桶的链表中
（2）局限性：网格索引在对象空间分布均匀时效率比较高
如果空间对象分配不均匀，那么最终会得到大量空白网格，浪费存储空间
网格尺寸不好确定，太大则索引效率低，太小则形成很多空白空格

2、树四叉树索引

类似于网格索引，也是对地理空间进行网格划分，对地理空间递归进行四分来构建四义树，直到自行设定的终止条件(比如每个节点关联图元的个数不超过3个，超过3个，就再四分)，最终形成一颗有层次的四叉树。每个叶子节点存储了本区域所关联的图元标识列表和本区域地理范围，非叶子节点仅存储本区域地理范围。由于四叉树的生成和维护比较简单，且当空问数据对象分布比较均匀时，基于四叉树的空问索引可以获得比较高的空间数据插入和查询效率。

B-Tree索引

大多数MySQL引擎都支持这种索引，对索引列是顺序组织存储的，很适合查找范围数据。如：像找出所有以I到K开头的名字“这样的查找效率会非常高。适用于全键值，键值范围或键前缀(最左前缀的查找)查找。

MYSQL索引（InnoDB）聚族索引

聚族索引不是一种单独的索引类型，而是一种数据存储方式。InnoDB的聚族索引在同一结构中保存了B-Tree索引和数据行。数据行存放在索引的叶子页中,术语"聚族"表示数据行和相邻的键值紧凑地存储在一起。存储引擎负责实现索引(不是所有的存储引擎都支持聚族索引)。
聚簇索引保证关键字的值相近的元组存储的物理位置也相同（所以字符串类型不宜建立聚簇索引，特别是随机字符串，会使得系统进行大量的移动操作）
倒排、空间、BTREE、HASH索引
一个表只允许一个主键索引，以b+树结构存储，索引上面已经存储了数据。查询的时间复杂度为树的高度
辅助索引，存储了主键的指向，查询时需要先找到辅助索引，然后根据辅助索引的值找到主键索引，然后再获取数据

哈希索引

哈希索引只包含哈希值和行指针，而不存储字段值。无法用于排序，不是按照索引值顺序存储的不支持部分索引列匹配查找(哈希索引是使用索引列的全部内容来计算哈希值得)、不支持任何范围查询，只支持等值比较查询，包括=、IN()、<=>

倒排、空间、BTREE、HASH索引