MySql 索引
索引类似于查字典时，根据页码可以快速的找到整页的数据。
InnoDB的每个索引对应一颗B+树，表本身就是以主键为索引的B+树。节点的大小是页的大小。
因此，索引可以分为两类:
-
聚集索引
主键，包含了整列的数据
-
二级索引
非主键索引的叶子节点内容是主键的值。
因此通过非主键索引的查询需要多搜索一次表，这被称为回表。
我们可以通过 explain sql 语句，获得查询计划，从而分析出查询实际走的是哪条索引。主要我们可以分析以下几个参数.
-
type 联接类型
一般来说，得保证查询至少达到range级别，最好能达到ref。
- all 最坏的情况,全表扫描
- index 和全表扫描一样。只是扫描表的时候按照索引次序进行而不是行。主要优点就是避免了排序, 但是开销仍然非常大。如在Extra列看到Using index，说明正在使用覆盖索引，只扫描索引的数据，它比按索引次序全表扫描的开销要小很多。
- range 范围扫描，一个有限制的索引扫描。
- ref 索引访问,所有匹配某个单个值的行。 非唯一性索引。
- eq_ref 最多只返回一条符合条件的记录。使用唯一性索引或主键查找时会发生 （高效）
- const 当确定最多只会有一行匹配的时候，MySQL优化器会在查询前读取它而且只读取一次，因此非常快。当主键放入where子句时，mysql把这个查询转为一个常量
- system const连接类型的一种特例，表仅有一行满足条件。
- Null 在执行阶段甚至用不到访问表或索引
-
key 索引
-
**key_len ** 使用的索引的长度
-
**ref ** 索引中查找值所用的列或常量
-
rows 为了找到所需的行而需要读取的行数，估算值，不精确。通过把所有rows列值相乘，可粗略估算整个查询会检查的行数
-
extra 额外信息，如using index、filesort等
- Using filesort 用了文件/内存来进行排序
- Using temporary 用临时表保存中间结果
- Using index 覆盖索引，无需回表
- Using where 使用了WHERE从句来限制哪些行将与下一张表匹配或者是返回给用户
- Using join buffer 使用了连接缓存：Block Nested Loop
B树将数据库分解成固定大小的块或页面，传统上大小为4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。
为了使数据库对崩溃具有韧性，B树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）（也称为重做日志（redo log））。
ElasticSearch 倒排索引
常规的索引是文档到关键词的映射，但是这样检索关键词的时候很费力，要一个文档一个文档的遍历一遍。于是人们发明了倒排索引,倒排索引是关键词到文档的映射 关键词——>文档。
一个倒排索引由文档中所有不重复词的列表构成，对于其中每个词，有一个包含它的文档列表。
所以我们需要分词器。
ElasticSearch的底层存储是LSM tree，核心特点：
- 第一：将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）；
- 第二：用批量写入代替随机写入，并且用预写日志 WAL 技术（Elasticsearch 中为 translog 事务日志）保证内存数据，在系统崩溃后可以被恢复；
- 第三：数据采取类似日志追加写的方式写入（Log Structured）磁盘，以顺序写的方式提高写入效率。
当查找数据库中不存在的键时，LSM树算法可能会很慢：您必须检查内存表，然后将这些段一直回到最老的（可能必须从磁盘读取每一个），然后才能确定键不存在。为了优化这种访问，存储引擎通常使用额外的Bloom过滤器。
LSM 的段的大小是不固定的。通常LSM树的写入速度更快，而B树的读取速度更快。
