聊聊数据库的那些索引
本文最后更新于：2024年4月14日 下午
作为后端开发工程师随着工作年限的增长，慢慢接触了许多数据库：
MySQL
MongoDB
InfluxDB
Elasticsearch（搜索引擎，姑且也算是一种nosql数据库）
随着业务特性不同，我在不同的项目里最终选择了不同的数据库作为核心数据存储。本文主要总结一下，这些数据库中主流存储引擎的底层索引结构。
B+树索引
B+ 树 是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
B+ 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。
MySQL的InnoDB 存储引擎使用的B+树作为底层的数据结构，这里不做赘述。
MongoDB 的 WiredTiger 存储引擎同样也是选择B+树作为底层的数据结构。
倒排索引
倒排索引 （英语：Inverted index），也常被称为反向索引 、置入档案 或反向档案 ，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构
Elasticsearch作为一个搜索引擎，是用倒排索引来构建自己的数据结构，以方便数据的检索。
InfluxDB 作为是一个时序数据库也用到了倒排索引，来进行其LSM引擎的构建。主要是为了支持不同tag 数据的多维度查询。
LSM树
LSM树（Log-Structured Merge Tree）存储引擎。代表数据库：nessDB、leveldb、Hbase等
LSM Tree 日志结构化合并树，核心思想的核心就是放弃部分读能力，换取写入的最大化能力。它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在磁盘中，等到积累到最后多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。
日志结构的合并树（LSM-tree）是一种基于硬盘的数据结构，与B-tree相比，能显著地减少硬盘磁盘臂的开销，并能在较长的时间提供对文件的高速插入（删除）。然而LSM-tree在某些情况下，特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。Bigtable在提供Tablet服务时，使用GFS来存储日志和SSTable，而GFS的设计初衷就是希望通过添加新数据的方式而不是通过重写旧数据的方式来修改文件。而LSM-tree通过滚动合并和多页块的方法推迟和批量进行索引更新，充分利用内存来存储近期或常用数据以降低查找代价，利用硬盘来存储不常用数据以减少存储代价。
磁盘的技术特性:对磁盘来说，能够最大化的发挥磁盘技术特性的使用方式是:一次性的读取或写入固定大小的一块数据，并尽可能的减少随机寻道这个操作的次数
- influxdb对LSM树进行了大量的优化
总结
参考文章
http://hbasefly.com/2018/03/27/timeseries-database-6/