汇总并对比几个数据库存储相关的知识 存储引擎数据结构
程序员文章站
2022-03-06 13:31:39
...
**包含广义数据库**：rocketmq(补在最后)-mysql-mongodb-hbase-lucene(ES)-redis，业务数据结构与文件系统存储两方面。
第一次看数据如何存储到文件中还是看rocketmq时（也可以看成某种数据库），它的存储功能里是顺序写消息文件，又有线程给数据建索引文件，文件中前一块是一个个固定字节的hash-slot，后一块是固定字节长度的消息地址数据的节点，文件们接在一起。通常内存中的结构，比如hashmap，树都是相对简单的，指针就是内存地址，有JVM帮你分配和回收。但文件里的就不一样了，考虑数据占用，所在文件与偏移量等。长度，占用与回收等更复杂的问题要自己设计了。
知识需要往深里学，这对于真正用好它们很重要，所有应用软件之中，数据库可能是最复杂的，用了很久却不知道其数据文件里是怎么存数据的。所以最近在看一些数据库存储引擎是如何组织数据的，比如一个mysql库中所有的表，所有索引，Undo等都可以存在一个文件中，那数据是如何组织的呢？
**数据组织非常琐碎的细节，小到几个字节存什么都讲究，本文不准备copy这些设计细节过来，也没时间太细，总结的是总体结构思想，在这基础上用好数据库就可以了。另外一些细节的文档只有说明没有why，这里也试着猜测一下。所看的资料可能版本不同，但本文重点是了解主要结构与思想，一些常见的问题比如为什么树，如何scan数据也就有个说法，有很多优化与适配业务特点也就懂了why了。**
在存储引擎工作前，先有wal机制记录日志（可靠与速度要求，我做业务组件时是用db记请求，再内存处理），再就是内存处理持久化，重点关注两个维度：
#### 存储引擎用的数据结构
https://www.cnblogs.com/niutao/p/10627217.html
#### 磁盘空间管理方式
数据也库，表，记录这样的切分，还有管理数据。如何写到硬盘文件中，不可能都顺序写入，如果利用删除后的空闲。内存与硬盘的页交换都是要考虑的问题。所有用过的数据空间，还有空闲删除的空间，也要标识并有链表串起来进行管理。空间是统一分配还是在一定的条线上分配也有讲究。这比序列化对象到文件复杂多了，当然简单的地方也就序列化一下的。
#### **总体结论**
存储引擎的其中一个工作，类似于大球场内划分区域，划分格子，划分座位，然后安排不同结构（比如树型）的组织人员入座。同组织的人员知道关联的人员坐在哪个位置上，也可能几个人坐一起，也可能不在一起。也许有人离开，空位也要合理处理给新人，还可能进一步调整碎片座位。
存储引擎管理人员也可能占用座位，也可能单独的地方。mysql前面的页，mongodb的ns文件，都是放管理数据的。如果是分布式系统，一般是放配置服务器，比如rocketmq，hbase，不与业务数据争机器，机器也不可靠，业务数据也备份。
存储引擎当然还负责业务数据及产生的索引数据，它们根据业务要求选择多种数据结构，但原始数据除了wal写日志外，还要把数据分到文件，写入磁盘。对于rocketmq，由于消息存新扔旧，所以有一个绝对编号，可以找到文件，可以找到物理offset。对于mongodb，数据是文件名+内部offset定位的，而对于mysql，由于Page是全局连续编号的最小单元且大小一样，所以数据指针是页号+页内offset，而不使用extent或者文件来定位。对于索引，rocketmq因为是索引头，索引slot，索引块都定长，所以索引文件内，数据之间存对方顺序号就能找到，还节约空间，因为可以算出物理offset。而如果数据之间关联，还跨文件，就需要象mongo那样的定位了。索引数据与业务数据一般分两个条线，即使msql的innodb用b+在叶子存数据的聚簇索引，也分成两条线的给磁盘空间的，因为索引可以定长，数据大小差别可能很大。
本文汇总了好多种广义数据库的存储，可以仔细口味各自作者如何考虑存放，变更，检索，作出特色选择的。
## 一、mysql的innodb引擎的数据组织
mysql有两个常用的存储引擎，可以按表配置。这里主要讲innodb。
InnoDB的每个数据文件都归属于一个表空间，不同的表空间使用一个唯一标识的space id来标记。例如ibdata1, ibdata2… 归属系统表空间，拥有相同的space id。用户创建表产生的ibd文件，则认为是一个独立的tablespace，只包含一个文件，如果搞分区表，就会有多个ibd文件了。而每一个表数据本身就是基于id的B+树，虽然在内存中建一个B+树相对容易，但这么多会变化的B+树要放在一个文件中存放，是巨大的挑战。
### 1. 总体介绍
文件肯定要合理的组织，分层次容纳表结点数据的，还要按需扩展。从逻辑上分：表空间，段，区，页，这样4个层次。同一个库里的表可以共享一个表空间，也可以一表一用户表空间配置。页是最小单位，16k一个进行编号，共2^32个，一个表空间的最大值为2^32*16kb=64TB。
一个用户表空间文件ibd，大约包含下面介绍的页（每个16K）来管理整个文件，而ibdata的前三个page和普通的用户表空间一样，都是用于维护和管理文件页，其它的页太复杂，就不具体说明了。
这几个特殊页直接操作用来管理其它空间分配。
### 2. 数据文件第一个16K的页
数据文件的第一个Page类型`FIL_PAGE_TYPE_FSP_HDR`，在创建一个新的表空间时进行初始化(`fsp_header_init`)，该page同时用于跟踪随后的256个Extent(约256MB文件大小)的空间管理，所以每隔256MB就要创建一个类似的数据页，类型为`FIL_PAGE_TYPE_XDES`。
> 可以理解为先有一个房管局的房子，里面有人记录总的房间数，所有安排满的特殊楼，空的特殊楼，还有256个人管理256个楼。
>
> 每个人记录，这个楼是否是某公司的段，楼状态，楼里的房间是否空闲。
>
> 之后再建一个房管局的房子，里面256个人再管理256个楼。
### 3. 第二个16K的页
第2个page类型为`FIL_PAGE_IBUF_BITMAP`，主要用于跟踪随后的每个page的change buffer信息，使用4个bit来描述每个page的change buffer信息。
> 可以理解为房管局房子后接着一个房子管理变化。后面的房管局房子后也都有。
### 4. 第三个16K页
数据文件的第3个page的类型为`FIL_PAGE_INODE`，用于管理数据文件中的segement，每个索引占用2个segment，分别用于管理叶子节点和非叶子节点。每个inode页可以存储`FSP_SEG_INODES_PER_PAGE`（默认为85）个记录。
### 5. 索引页FIL_PAGE_INDEX
ibd文件中真正构建起用户数据的结构是BTREE，在你创建一个表时，已经基于显式或隐式定义的主键构建了一个btree，其叶子节点上记录了行的全部列数据（加上事务id列及回滚段指针列）。每个btree使用两个Segment（段）来管理数据页，一个管理叶子节点，一个管理非叶子节点，每个segment在inode page中存在一个记录项，在btree的root page中记录了两个segment信息。
包含：
### 6. 小结
#### 空间层次
数据存入文件重点是空间的划分，首先有一个适当的与内存交换最小的存储单位页。就是一个个房间。
考虑页比较小，放管理数据还可以，真正的大数据量与连续存储，又有于区（extent）这个概念，含64个连续page。就是人多了，就整栋楼的分。
考虑到空间要分给不同的树，从树的维度要有一个划分与管理，所以有了段(segement)的概念。段里有页，也有区。一个树的叶子与非叶子差别比较大，分别算一条段。
#### 层次的链表关系
这些层次的空间，目前都还没有树结点数据什么事。只是空间上的管理。而且空间上要管理空的区，空的页，满的区，半满的...分别建立链表。比如房管局管着空楼，空的特殊楼，满的特殊楼这样的链表。分出去的楼不管了。而Inoded页中的段的维度又管理着分给所在公司段的空的，不空的，满的楼的链表。空楼分给公司段后也可能是空的，不过挂在不同的链表上了。
InnoDB的数据在内存缓冲区是由B+树组织的，而B+树中的每一层的页是由双向链表串起来，因为每个页header有指向上一个和下一个页的指针；这种结构可以提升全表扫描的效率；
#### 用户数据
用户数据存在索引页上的适当部分，每页有专门的最小值与最大值记录，中间链接起来的是真正用户记录。
For both leaf and non-leaf pages, each record (including the infimum and supremum system records) contain a “next record” pointer, which stores an offset (within the page) to the next record. The linked list starts at infimum and links all records in ascending order by key, terminating at supremum. The records are not physically ordered within the page (they take whatever space is available at the time of insertion); their only order comes from their position in the linked list.
页内数据按Key值升序，并不是物理排序，插入时只找可用空间放，一个记录存另一个记录的页内offset。
因为一页的大小被限制到16KB（16384字节），但是一个字段的长度不能超过65535字节。所以这里会产生一个行溢出的问题，所以里面处理的方式，在不同格式下会有些差异。大体上就是将超出的部分放在别的页里面。原本的列里面保存的是别的页上面的地址。
#### 其它
看来来，比rocketmq的内存映射文件处理复杂，比固定索引文件长度的复杂太多了，这只是存储方面。所以存binlog，redo，undo等日志和内存中处理就快多了，还有checkpoint确认日志中的写入数据文件，如果都等复杂的文件存储处理完就慢了。
不过从更大的层面，也有相似性，也有客户端管理，权限，请求处理，事务等，也许hash索引更相似。后面提到mongodb的mmap存储引擎也用了内存映射文件处理。
#### 参考
http://mysql.taobao.org/monthly/2016/02/01/
https://dev.mysql.com/doc/refman/5.7/en/innodb-file-space.html
https://www.cnblogs.com/wcwen1990/p/6655386.html
https://www.jianshu.com/p/aab602b842c2
https://www.cnblogs.com/ijia/p/10739192.html
https://yq.aliyun.com/articles/51133
https://blog.51cto.com/59090939/1955122
## 二、mongodb的文件存储
为了能够更好的支持大数据或者实时应用，现在我们通常需要非关系型的、动态的schema，这样就没有必要进行表关联查询。它不再需要遵循 SQL 和关系型数据库的体系，可以更*对特定场景进行优化，而在 MongoDB 假设的场景中遍历数据并不是常见的需求，它追求的是读写单个记录的性能。
MongoDB 为于存bson文档数据，没有schema，理论上可以随便存不同结构的文档数据，它减少了一些关系数据库必要的限制，那就需要另外的存储方式提高读写速度了。它的id索引采用特殊的b-tree，不是关系数据库的b+tree，还有一个LSM 树不介绍了。关系数据库利用了b+树的叶子节点相连，在方便查询同时也非常方便遍历这个需求，但MongoDB 认为查询单个数据记录远比遍历数据的查询更加常见，但对于遍历数据也需要有相对较好的性能支持，所以用b树就行了。如果用hash，遍历就太差了。
它也有两个主要的存储引擎，分别是MMAPv1 和wiredTiger。这里介绍老的 MMAPv1 存储引擎的数据组织方式，虽然会被废弃，但资料比较多，方便学习，这时数据文件使用 mmap 映射到内存空间进行管理，内存的管理（哪些数据何时换入/换出）完全交给OS管理。两者的对比可以看参考。
### 1. 文件空间层次
MongoDB 在库之下的Collection与Document概念分别对应rdb中的table与row。存储层次分别为：库，Namespace（同一表数据，索引各不同ns），区（extent），record。
一个mongodb服务器上可以建多个库Database(DB) ，每个库（比如mydb名字的库）由一个.ns文件及若干个数据文件组成，数据文件从0开始编号，依次为mydb.0、mydb.1、mydb.2等，文件大小从64MB起，依次倍增，最大为2GB。不同库之间是文件隔离的，所以最高层次就是库，除了ns文件，只是切分扩展。
数据文件中有一个个的extent，它们可以属于不同的namespace，即一个新开辟的文件空间可以存库里的任何表数据。在ns中记录着同一个表的开始与结束的extent位置，同一个表的extent形成双向链表，这样就从表的角度串起了所有的extent。一个extent里都是同一个表的数据record。
### 2. 关联关系
上面已经提到了一部分，再明确一下。
一个namespace串起不同文件上的extent，一个extent里的记录也自己串起来。这样当对此collection进行scan操作时（比如全表扫描），可以提供很大的便利性。
每个数据文件包含一个固定长度头部DataFileHeader，Header 中包含数据文件版本、文件大小、未使用空间位置及长度、空闲 extent 链表起始及结束位置。extent被回收时，就会放到数据文件对应的空闲 extent 链表里。说明基本上都有链表来管理空间层次。
一个 namespace下的所有的已删除记录（可以回收并复用的存储空间）以单向链表的形式，为了最大化存储空间利用率，不同size（32B、64B、128B…）的记录被挂在不同的链表上，可以复用空间。这几个空闲链的头存在ns中的这个namespace中管理，记录着文件号与偏移位置。
新的记录插入到extent中，可能找空的地方，也可能顺序的插入，我猜测不管插到哪个extent中的哪个物理位置，都在这个extent中的record链接的最后。现在查到了源码如下：
### 3. 索引的数据
The index namespace is a* **combination of the database name and the name of the collection or index***, like so: [database-name].[collection-or-index-name].*
官方文档写道MongoDB defines indexes at the collection level and they are supported by any field or embedded field of the documents in the collection.（索引定义在collection的层级，可建在任何字段或者嵌入的字段上）
每一个索引也对应于一个namespace ,如db.coll 这个collection的索引{x:1,y:1},其索引保存到了namespace :
db.coll.$x_1_y_1。
这里有b树构建源码解读：http://www.itboth.com/d/ZfMNRb/system-sharding-mongodb-insert 由于mmap，产生的Every b-tree bucket is allocated as needed and thus has it's own location within the data file. **但具体的信息没找到足够细节相关的资料，C++又不懂。英文网页有一点点信息**
https://dba.stackexchange.com/questions/65180/ （how-are-mongodb-indexes-stored-on-disk）中提到：
```html
there is a logical structure within the files, extents, that are the real units of storage. That and far more is covered in detail by [this presentation](http://www.mongodb.com/presentations/storage-engine-internals) by Mathias Stearn - one of the kernel developers at MongoDB.
Indexes are just another (structured) form of data in MongoDB and they are stored in linked extents throughout the file.
（数据文件中的extents是真实存在的存储单元，索引也是在整个文件所链接着的extent中存储的。）索引的结构估计就是BtreeBucket。
```
刚找到这个：http://zhangliyong.github.io/posts/2014/02/19/mongodb-index-internals.html
以上算是index的存储基本明白了。
### 4. 其它
文件空间还是按链表进行组织，按namespace有不同的条线串起来，条线上的数据又有数据的组织方式，比如数据条线的record在extent内小双向链表，索引条线又是另外的指针地址相连。还有空闲的也链表串起来，这点与mysql大体相似。
关于插入新record后遍历顺序，网上有人问https://*.com/questions/11599069/。查到sort如果没有指定，是按自然顺序，什么是自然顺序，一般是插入顺序。但会利用删除记录后的空闲空间，所以不是全局最后，而可能在其它extent中的最后记录后面。Capped Collections除外。
mongodb的索引很丰富，包括有TTL Indexes。可以设置多少时间后删除，也可以设置成未来要删除的时间，0秒后删除。
https://blog.csdn.net/u010385646/article/details/52493464（mmap方式介绍）
https://blog.csdn.net/tengxy_cloud/article/details/52808462
https://mongoing.com/archives/35143
http://www.mongoing.com/blog/file-storage
https://www.jb51.net/article/117764.htm
https://yq.aliyun.com/articles/11025 (源码元数据定义)
https://blog.csdn.net/n88Lpo/article/details/90276252
https://www.cnblogs.com/linguoguo/p/12291686.html
https://www.jb51.net/article/65634.htm
## 三、Hbase
HBase – Hadoop Database，是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统，利用HBase技术可在廉价PC Server上搭建起大规模结构化存储集群。hbase是建立在hdfs上的数据库，面向列。id是保证全局顺序的。分布在region中，数据多了会分裂region。
id设计很有讲究，不能局部过热写入，还能按id范围查找。
#### 1. 逻辑层次
一个比较大的不同时，一个hfile文件对应最小的层次。而mysql中，一个文件对应一个表空间。mongodb中，几个切分的文件拼起来，对应一个库。那么问题来了，其实层次的内容，包含关系存在哪？
1. Region
table在行的方向上分隔为多个Region。Region是HBase中分布式存储和负载均衡的最小单元，即不同的region可以分别在不同的Region Server上，但同一个Region是不会拆分到多个server上。Region按大小分隔，表中每一行只能属于一个region。随着数据不断插入表，region不断增大，当region的某个列族达到一个阈值（默认256M）时就会分成两个新的region。每个HStore对应了Table中的一个column family的存储，可以看出每个columnfamily其实就是一个集中的存储单元，因此最好将具备共同IO特性的column放在一个column family中，这样最高效。
2. Store
每一个region有一个或多个store组成，至少是一个store，hbase会把一起访问的数据放在一个store里面，即为每个ColumnFamily建一个store（即有几个ColumnFamily，也就有几个Store）。一个Store由一个memStore和0或多个StoreFile组成。MemStore是 Sorted Memory Buffer，用户写入的数据首先会放入MemStore，当MemStore满了以后会Flush成一个StoreFile（底层实现是HFile）。HBase以store的大小来判断是否需要切分region。
3. MemStore
memStore 是放在内存里的。保存修改的数据即keyValues。当memStore的大小达到一个阀值（默认64MB）时，memStore会被flush到文件，即生成一个快照。目前hbase 会有一个线程来负责memStore的flush操作。
4. StoreFile
memStore内存中的数据写到文件后就是StoreFile（即memstore的每次flush操作都会生成一个新的StoreFile），StoreFile底层是以HFile的格式保存。
5. HFile
HFile是HBase中KeyValue数据的存储格式，是hadoop的二进制格式文件。一个StoreFile对应着一个HFile。而HFile是存储在HDFS之上的。HFile文件格式是基于Google Bigtable中的SSTable。
首先HFile文件是不定长的，长度固定的只有其中的两块：Trailer和FileInfo。Trailer中又指针指向其他数据块的起始点，FileInfo记录了文件的一些meta信息。
由于是分布式系统，Region是HBase中分布式存储和负载均衡的最小单元，也就是Region（一个表的一部分排序的记录），可以在RegionServer机器间移动。
#### 2. 数据持久化
用到Memstore最主要的原因是：存储在HDFS上的数据需要按照row key 排序。而HDFS本身被设计为顺序读写(sequential reads/writes)，不允许修改。这样的话，HBase就不能够高效的写数据，因为要写入到HBase的数据不会被排序，这也就意味着没有为将来的检索优化。为了解决这个问题，HBase将最近接收到的数据缓存在内存中(in Memstore)，在持久化到HDFS之前完成排序，然后再快速的顺序写入HDFS。
数据是排序的，每个region内的数据的key最小值与最大值范围是有记录的。zk上应该有记录meta数据的。
https://www.cnblogs.com/163yun/p/9020629.html（hfile格式）
HBase中定义了8种BlockType，每种BlockType对应的block都存储不同的数据内容，有的存储用户数据，有的存储索引数据，有的存储meta元数据。对于任意一种类型的HFileBlock， 都拥有相同结构的BlockHeader ， 但是BlockData结构却不相同。
#### 3. 数据操作定位
Client端想要插入，删除，查询数据都需要先找到相应的RegionServer。很多文章从zk的meta数据进行了说明，包括三层与新的二层查找。但我有疑问，找到了regionserver后，它又怎么定位对数据进行操作呢？这个没的找到答案，单机的系统可以找文件，找区，找偏移量，但这个情况下呢？但我想到了regionserver可以宕机，看来它只管按hdfs来读写数据就行了。它本身不会存任何自己独有的管理信息。
https://www.cnblogs.com/zwgblog/p/5733583.html (meta表)
https://jingyan.baidu.com/article/7c6fb42832124a80642c90f4.html（regionserver宕机）
#### 4. 数据模型操作
数据模型的四个主要操作是Get，Put，Scan和Delete。可以通过Table实例进行操作。HBase是否支持join是一个常见的问题，答案是没有，至少没办法像RDBMS那样支持。
https://zhuanlan.zhihu.com/p/47074785（优化的目标与办法）
rowkey的比较规则是整个HBase数据模型的核心，直接影响了整个请求路由体系的设计、读写链路、rowkey设计、scan的使用等，贯穿整个HBase。对于用户而言，深入理解这个规则及其应用有助于做出良好的表设计，写出精准、高效的scan。
当大量请求访问HBase集群的一个或少数几个节点，造成少数RegionServer的读写请求过多、负载过大，而其他RegionServer负载却很小，这样就造成**热点现象**。大量访问会使热点Region所在的主机负载过大，引起性能下降，甚至导致Region不可用。所以我们在向HBase中插入数据的时候，应尽量均衡地把记录分散到不同的Region里去，平衡每个Region的压力。
RowKey经验：https://zhuanlan.zhihu.com/p/69462736
#### 5. 其它
一个表的列族不能太多，一般一个。由于列簇共享region，由于关联性在分裂与flush时影响导致性能下降。都是廉价机集群，性能是靠分担才上去的。
#### 6. 参考：
https://www.cnblogs.com/simple-focus/p/6198329.html
https://blog.csdn.net/lijingjingchn/article/details/89924181
https://blog.csdn.net/xiaoshunzi111/article/details/69844526
待补充...
## 四、lucene---ElasticSearch
lucene作为全文检索工具，数据的保存也很非常有特色的，实际上也是非常复杂的，本文只汇总整体关系，从我们要存什么开始。而多数文章是使用，或者讲述倒排表和高效的词典的FST查找之类的方面，讲总体的不多，可能是比较简单？首先用一个Lucene多字段不同Analyzer分词器的索引的创建和查询例子，来引出设计上的特点。
#### 1. 引出业务概念与数据层次
问题来源于：https://bbs.csdn.net/topics/391841943，虽然楼主开始的用法不对，却也说明了几个数据关系。
IndexWriter负责把一个文档进行索引并写入一个文件夹目录。目前先在这个层次内进行说明。一个索引文件的目录，由一个IndexWriter把一类的Document写进去。这个层次类似于数据库表这个层次的概念。
Document由一到多个Field组成，类似于字段，每个字段有名字与值，可以选择是否进行保存，是否进行分词等，而且可以设置不同的字段用不同的分词器。
原文作者不知道PerFieldAnalyzerWrapper，可用于同一类型Document的各字段分词。而是分成多个不同的Document，这个层面用不同的分词器，最后想用MultiReader垮文档组合读，而QueryParser解析用户查询输入词，这又不可能按Document不同进行不同的分词切分（因为作者在更细的层级实现了不同切分），所以搞不下去了。
所以，在一种Document这个层面，要存储的东西有：
**原始数据：**
这种Document的每一个Document的有字段的原始数据，可能要保存。有时候使用时，可只保存一个id，其它原始数据存在其它数据库里。存的方式有正向文件（行式存储且多文档一起压缩），列式存储两种。前者适合展示倒排查到的文档，后者可对检索结果进行分类、排序、数学计算等聚合操作。
**倒排表**：
字段可以进行不同分词器的分词后，建倒排表。表明一个词，出现在哪些文件的这个字段数据的什么位置及次数之类的。每一个要建索引的字段都产生一个倒排表。这类Document多个字段有索引，就产生多个倒排表。
#### 2. 倒排表存储方式
还是限于一种Document，即一个文件目录，一个IndexWriter的级别。首先发现就是文档类型太多了。
一个字段所建的倒排表，是所出现的一堆的词与每个词在哪些文档及位置的关系表。词要存，之间的关系要存。lucene用了几个不不同后缀的文件，拆成三个层级来存。
照这个思想，其实hash方式也可以拆开，hash部分一个文件，冲突链表一个文件，内存只加载前面一个也可以小很多了。另外要提的是，不可能所有的Document放一起，它还有一个维度要segement段的概念，段会合并，相应的倒排表也会合并。这个维度在前面提到的数据库中也有，比如hbase的region，比如monodb中的extent。Segment上每个字段都有自己的一个FST（FSTIndex）记录在`.tip`上，所以也只是同一字段的合并FST，不同字段还是分开的。不过都放在一个文件上。具体文件怎么划空间就不细看了，无法研究那么透彻。
一个倒排表就存了这么多信息，所以它的检索过程分为三个步骤：
#### 3. 原始数据存储方式
##### **正向文件存储**
Lucene对原始文档也提供了存储功能，存放是**行式存储**，并且为了提高空间利用率，是多文档一起压缩。它存储特点就是分块+压缩。fdt文件就是存放原始文档的文件，它占了索引库90%的磁盘空间，fdx文件为索引文件，通过文档号（自增数字）快速得到文档位置，它们的文件结构如下：
既然多文档压缩分块了，所以就要从文档号到文档位置的索引，所以查找文档，就分为三步：
第一步二分查找block，定位属于哪个block。
第二步就是根据从block里根据每个chunk的起始文档号，找到属于哪个chunk和chunk位置。
第三步就是去加载fdt的chunk，找到文档。
##### 列式存储DocValues
需要对检索结果进行分类、排序、数学计算等聚合操作时需要文档号到值的快速映射，而原先不管是倒排索引还是行式存储的文档都无法满足要求。比如有个部门字段没有分词，但建了索引，所以有倒排表，可以按部门名称找出相关的文档，对其中的一些字段进行聚合运算。
**在我看来，这就是抢数据库的饭碗，为何不把原始数据存储放其它类型的数据库中，发挥各自强项呢？这个只查出id就可以了。如果原始数据中还想有关联检索，是否lucene也考虑增加功能呢？**还是说说结构吧：
4.0版本后Lucene推出了DocValues来解决这一问题，它和FieldCache一样，都为列式存储，但它有如下优点：
DocValues这种实现方法只比内存FieldCache慢大概10~25%，但稳定性却得到了极大提升。
Lucene目前有五种类型的DocValues：NUMERIC、BINARY、SORTED、SORTED_SET、SORTED_NUMERIC，针对每种类型Lucene都有特定的压缩方法。
对DocValues的应用，ElasticSearch功能实现地更系统、更完整，即ElasticSearch的Aggregations——聚合功能。
#### 4. Elasticsearch
Elasticsearch 是一个分布式可扩展的实时搜索和分析引擎,一个建立在全文搜索引擎 Apache Lucene(TM) 基础上的搜索引擎。特点是：
其实有特色的全文检索东西都在lucene中，这里只写一点，有这样一个所谓比较：
其实我感觉不准确，前面讲lucene时，我把一种Docments当成一个表的。这里的tye这个层次怎么理解呢？我认为是抽象类与多个具体类这样的关系，具体实现与存储上的问题暂不分析了，除非真正了解这么深。
**type的使用**
一个例子就清楚了。比如商品index，里面存放了所有的商品数据，商品document
但是商品分很多种类，每个种类的document的field可能不太一样，比如说电器商品，可能还包含一些诸如售后时间范围这样的特殊field；生鲜商品，还包含一些诸如生鲜保质期之类的特殊field
不同 type 里的字段需要保持一致。例如，一个 index 下的不同 type 里有两个名字相同的字段，他们的类型（string, date 等等）和配置也必须相同。这难道认为是表的概念吗？除非理解为1对1的公共字段与非公共字段的一组相关表。
只在某个 type 里存在的字段，在其他没有该字段的 type 中也会消耗资源。这是 Lucene Index 带来的常见问题：它不喜欢稀疏。由于连续文档之间的差异太大，稀疏的 posting list 的压缩效率不高。这个问题在 doc value 上更为严重：为了提高速度，doc value 通常会为每个文档预留一个固定大小的空间，以便文档可以被高速检索。这意味着，如果 Lucene 确定它需要一个字节来存储某个数字类型的字段，它同样会给没有这个字段的文档预留一个字节。未来版本的 ES 会在这方面做一些改进，但是我仍然建议你在建模的时候尽量避免稀疏。
https://blog.csdn.net/zteny/article/details/82857080
https://blog.csdn.net/njpjsoftdev/article/details/54015485
https://baijiahao.baidu.com/s?id=1666739392937388743&wfr=spider&for=pc
https://www.jianshu.com/p/044d4b1adc89
## 五、redis
redis作为内存数据库，就只从编程语言的角度说说内存中的数据结构，至于快照存盘设计有空再补充。
redis用C语言写的，有五大数据结构，但底层是怎样的数据结构呢，他们和我们java中的HashMap、List、等使用的数据结构有什么区别呢？
### 1. 基本数据结构
当看到ziplist被封装在quicklistNode中，再增加一些管理数据并串起链表，有点象包装第三方的对象增加属性的类。大链接里的小数组，又联想到前面extent中的page这样的大链接里面小链接的形式，也是一种分层架构思想的体现。
### 2. 对应关系
多种实现是因为有使用条件，条件上的一些阈值可以修改。
参考：
https://zhuanlan.zhihu.com/p/71057875
https://www.cnblogs.com/javazhiyin/p/11063944.html
## 六、rocketmq
消息是顺序写文件的，这样很快，而【消息信息】要分队列存放供消费，还要索引来快速拿到消息，所以有独立的线程从原始消息文件来建消息索引与各个队列。索引文件由头+多个hashslot+多个消息数据块组成（40byte+?*4+*?20）。类似hashmap方式。
### 1. 索引主要类与核心操作
#### IndexHeader类
每个索引文件有40个byte的头，包括开始结束时间各8个，开始结束物理位置各8个，hashslot数与包含的索引数是整数，4个byte，共4*8+4+4=40个byte。
只需要从对应文件映射出来mappedByteBuffer，并slice出的一个byteBuffer来操作。用put/get指定位置的long/int就设/取值了。slice是自己的位置，但与相同的操作对象。
IndexHeader类，有这些属性，又持有byteBuffer，就可以初始化对象时加载文件中的值，也可以操作中设置新值到文件中。
#### IndexFile类
它持有mappedFile类，以及这个类的FileChannel与mappedByteBuffer，这里是引用，也可以当成是继承吧，反正核心的东西我直接持有了。
建一个新的IndexFile，等于新建一个以offset为名字的可读写的文件并映射内存mappedByteBuffer。前面讲这个类把mappedByteBuffer slice了一下，等于一部分交给IndexHeader来管理了。剩下的部分自己来管理。看看它的两个主要操作：
#### 建索引
putKey(String, long, long)，参数：key 物理offset 时间
#### 取值
selectPhyOffset(List<Long>, String, int, long, long, boolean)
### 2. 特点说明
两个操作类，都持有mappedByteBuffer，分别操作不同部分。分工明确。
写索引时，在slot位置记录自己排号，就是第几个，不是具体offset位置，这样数字比较小，offset可以计算出来。如果有冲突，新写的占用slot，但后面数据中有4byte有记录前一个的排号。如果按hash找出来，但key不对，就拿出前一个排号再查key对不对，这样直到找到。算是链表方式。
除了生成索引，还要生成队列，按topic与queueId产生一组文件，由ConsumeQueue类管理
第一次看数据如何存储到文件中还是看rocketmq时（也可以看成某种数据库），它的存储功能里是顺序写消息文件，又有线程给数据建索引文件，文件中前一块是一个个固定字节的hash-slot，后一块是固定字节长度的消息地址数据的节点，文件们接在一起。通常内存中的结构，比如hashmap，树都是相对简单的，指针就是内存地址，有JVM帮你分配和回收。但文件里的就不一样了，考虑数据占用，所在文件与偏移量等。长度，占用与回收等更复杂的问题要自己设计了。
知识需要往深里学，这对于真正用好它们很重要，所有应用软件之中，数据库可能是最复杂的，用了很久却不知道其数据文件里是怎么存数据的。所以最近在看一些数据库存储引擎是如何组织数据的，比如一个mysql库中所有的表，所有索引，Undo等都可以存在一个文件中，那数据是如何组织的呢？
**数据组织非常琐碎的细节，小到几个字节存什么都讲究，本文不准备copy这些设计细节过来，也没时间太细，总结的是总体结构思想，在这基础上用好数据库就可以了。另外一些细节的文档只有说明没有why，这里也试着猜测一下。所看的资料可能版本不同，但本文重点是了解主要结构与思想，一些常见的问题比如为什么树，如何scan数据也就有个说法，有很多优化与适配业务特点也就懂了why了。**
在存储引擎工作前，先有wal机制记录日志（可靠与速度要求，我做业务组件时是用db记请求，再内存处理），再就是内存处理持久化，重点关注两个维度：
#### 存储引擎用的数据结构
- - 哈希存储（比如rocketmq的索引用了hashmap）插入以及查询，哈希表的复杂度都是O(1)，但不支持顺序扫描。
- - B+树存储（一般的关系数据库，比如mysql）不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针）。
- - B树存储（比如mongodb）支持单条记录的增、删、读、改操作，一定程度支持顺序扫描。
- - LSM树（Log-Structured Mergetree，比如Hbase）同样支持增、删、读、改、顺序扫描操作，而且通过批量存储技术规避磁盘随机写入问题。LSM树牺牲了部分读性能，用来大幅提高写性能。
https://www.cnblogs.com/niutao/p/10627217.html
#### 磁盘空间管理方式
数据也库，表，记录这样的切分，还有管理数据。如何写到硬盘文件中，不可能都顺序写入，如果利用删除后的空闲。内存与硬盘的页交换都是要考虑的问题。所有用过的数据空间，还有空闲删除的空间，也要标识并有链表串起来进行管理。空间是统一分配还是在一定的条线上分配也有讲究。这比序列化对象到文件复杂多了，当然简单的地方也就序列化一下的。
- - mysql如果只用共享表空间，那一个文件对应所有表数据与管理，还分为页，区，段，表空间层级。
- - 有mongodb使用内存映射文件（这点与rocketmq一样），文件是编号连在一起的，不同的库一批文件，文件里还要为表进行块的切分。如果把一个文件当成机器的话，这就有点分布式分配的味道了。为了mongodb的文档数据略增加后原地保存，可能还提供一定的padding空间。
- - 有hbase利用hdfs，一个文件里只会是同一个列族的数据...
#### **总体结论**
存储引擎的其中一个工作，类似于大球场内划分区域，划分格子，划分座位，然后安排不同结构（比如树型）的组织人员入座。同组织的人员知道关联的人员坐在哪个位置上，也可能几个人坐一起，也可能不在一起。也许有人离开，空位也要合理处理给新人，还可能进一步调整碎片座位。
存储引擎管理人员也可能占用座位，也可能单独的地方。mysql前面的页，mongodb的ns文件，都是放管理数据的。如果是分布式系统，一般是放配置服务器，比如rocketmq，hbase，不与业务数据争机器，机器也不可靠，业务数据也备份。
存储引擎当然还负责业务数据及产生的索引数据，它们根据业务要求选择多种数据结构，但原始数据除了wal写日志外，还要把数据分到文件，写入磁盘。对于rocketmq，由于消息存新扔旧，所以有一个绝对编号，可以找到文件，可以找到物理offset。对于mongodb，数据是文件名+内部offset定位的，而对于mysql，由于Page是全局连续编号的最小单元且大小一样，所以数据指针是页号+页内offset，而不使用extent或者文件来定位。对于索引，rocketmq因为是索引头，索引slot，索引块都定长，所以索引文件内，数据之间存对方顺序号就能找到，还节约空间，因为可以算出物理offset。而如果数据之间关联，还跨文件，就需要象mongo那样的定位了。索引数据与业务数据一般分两个条线，即使msql的innodb用b+在叶子存数据的聚簇索引，也分成两条线的给磁盘空间的，因为索引可以定长，数据大小差别可能很大。
本文汇总了好多种广义数据库的存储，可以仔细口味各自作者如何考虑存放，变更，检索，作出特色选择的。
## 一、mysql的innodb引擎的数据组织
mysql有两个常用的存储引擎，可以按表配置。这里主要讲innodb。
InnoDB的每个数据文件都归属于一个表空间，不同的表空间使用一个唯一标识的space id来标记。例如ibdata1, ibdata2… 归属系统表空间，拥有相同的space id。用户创建表产生的ibd文件，则认为是一个独立的tablespace，只包含一个文件，如果搞分区表，就会有多个ibd文件了。而每一个表数据本身就是基于id的B+树，虽然在内存中建一个B+树相对容易，但这么多会变化的B+树要放在一个文件中存放，是巨大的挑战。
### 1. 总体介绍
文件肯定要合理的组织，分层次容纳表结点数据的，还要按需扩展。从逻辑上分：表空间，段，区，页，这样4个层次。同一个库里的表可以共享一个表空间，也可以一表一用户表空间配置。页是最小单位，16k一个进行编号，共2^32个，一个表空间的最大值为2^32*16kb=64TB。
> 对比一下：某地区房管局要建房子，再要分给各个大公司(table)的很多人员(node)。最小分配单位的一套房（page页/块，全局有编号的）。一个公司是树型（B+）组织，分为领导层段(segemnet)与员工段，上级知道下级的房间号的床位，员工由于携带针机器，占用空间不定。而区（extent）是包含一定数量房子的单个的楼，放不下人员了就要开拓新的楼出来。 > > 一般来说同一公司的领导层段，都在一些楼里；而员工段都在另一些楼里，不能混住。不过有特殊的楼，它里面的房子可以给不同的段用的，因为新公司的一个段刚开始时人少，不给整栋楼的，先分给这种特殊楼的32个房子用，用完才分给楼。
一个用户表空间文件ibd，大约包含下面介绍的页（每个16K）来管理整个文件，而ibdata的前三个page和普通的用户表空间一样，都是用于维护和管理文件页，其它的页太复杂，就不具体说明了。
这几个特殊页直接操作用来管理其它空间分配。
### 2. 数据文件第一个16K的页
数据文件的第一个Page类型`FIL_PAGE_TYPE_FSP_HDR`，在创建一个新的表空间时进行初始化(`fsp_header_init`)，该page同时用于跟踪随后的256个Extent(约256MB文件大小)的空间管理，所以每隔256MB就要创建一个类似的数据页，类型为`FIL_PAGE_TYPE_XDES`。
> 可以理解为先有一个房管局的房子，里面有人记录总的房间数，所有安排满的特殊楼，空的特殊楼，还有256个人管理256个楼。
>
> 每个人记录，这个楼是否是某公司的段，楼状态，楼里的房间是否空闲。
>
> 之后再建一个房管局的房子，里面256个人再管理256个楼。
### 3. 第二个16K的页
第2个page类型为`FIL_PAGE_IBUF_BITMAP`，主要用于跟踪随后的每个page的change buffer信息，使用4个bit来描述每个page的change buffer信息。
> 可以理解为房管局房子后接着一个房子管理变化。后面的房管局房子后也都有。
### 4. 第三个16K页
数据文件的第3个page的类型为`FIL_PAGE_INODE`，用于管理数据文件中的segement，每个索引占用2个segment，分别用于管理叶子节点和非叶子节点。每个inode页可以存储`FSP_SEG_INODES_PER_PAGE`（默认为85）个记录。
> 理解为这个房子里有85个人，可以管理85个段，每一个公司两个段。如果公司50个的话，这里放不下，会有新的房子并再有85个人。这些用完85人的房子与有空的会记录在第一个房管局房子里。 > > 85个人记什么呢？每个人记录管理哪个公司的什么段，就是段ID。分配给这个段的楼，分住满的，没满的，空的。还有记录32个特殊楼的房子。因为给公司段先分特殊楼的房子，再分楼。 当创建一个新的索引时，实际上构建一个新的btree(`btr_create`)，先为非叶子节点Segment分配一个inode entry，再创建root page，并将该segment的位置记录到root page中，然后再分配leaf segment的Inode entry，并记录到root page中。 > 理解为：给新公司分配时，先让85人中的空闲的人来记录，给领导段先分一个特殊楼的房子，再员工段找一个空闲的人来记录。这个特殊房子里，另有人记录领导段与员工段都是85人中的谁在记录。
### 5. 索引页FIL_PAGE_INDEX
ibd文件中真正构建起用户数据的结构是BTREE，在你创建一个表时，已经基于显式或隐式定义的主键构建了一个btree，其叶子节点上记录了行的全部列数据（加上事务id列及回滚段指针列）。每个btree使用两个Segment（段）来管理数据页，一个管理叶子节点，一个管理非叶子节点，每个segment在inode page中存在一个记录项，在btree的root page中记录了两个segment信息。
包含：
- - Page Header：38个字节来描述头信息，页号，类型等
- - Index Header：记录数，目录slot数，最近插入位置，索引的ID
- - Segment Info：20个字节描述段信息，仅在Btree的root Page有。另10个字节的inode信息，找到85个人之一在哪个页的位置。
- - 系统记录：该page上的极小值和极大值。
- - 用户记录：真正的用户记录了，可以是非叶子节点的Node指针信息，也可以是只包含有效数据的叶子节点记录。
- - Free space：一块完整的未被使用的空间，范围在页内最后一个用户记录和Page directory之间。
- - Page directory：页内构建的一个很小的索引(sparse index)来辅助二分查找。
- - FIL Trailer：文件页的末尾保留了8个字节
### 6. 小结
#### 空间层次
数据存入文件重点是空间的划分，首先有一个适当的与内存交换最小的存储单位页。就是一个个房间。
考虑页比较小，放管理数据还可以，真正的大数据量与连续存储，又有于区（extent）这个概念，含64个连续page。就是人多了，就整栋楼的分。
考虑到空间要分给不同的树，从树的维度要有一个划分与管理，所以有了段(segement)的概念。段里有页，也有区。一个树的叶子与非叶子差别比较大，分别算一条段。
#### 层次的链表关系
这些层次的空间，目前都还没有树结点数据什么事。只是空间上的管理。而且空间上要管理空的区，空的页，满的区，半满的...分别建立链表。比如房管局管着空楼，空的特殊楼，满的特殊楼这样的链表。分出去的楼不管了。而Inoded页中的段的维度又管理着分给所在公司段的空的，不空的，满的楼的链表。空楼分给公司段后也可能是空的，不过挂在不同的链表上了。
InnoDB的数据在内存缓冲区是由B+树组织的，而B+树中的每一层的页是由双向链表串起来，因为每个页header有指向上一个和下一个页的指针；这种结构可以提升全表扫描的效率；
#### 用户数据
用户数据存在索引页上的适当部分，每页有专门的最小值与最大值记录，中间链接起来的是真正用户记录。
For both leaf and non-leaf pages, each record (including the infimum and supremum system records) contain a “next record” pointer, which stores an offset (within the page) to the next record. The linked list starts at infimum and links all records in ascending order by key, terminating at supremum. The records are not physically ordered within the page (they take whatever space is available at the time of insertion); their only order comes from their position in the linked list.
页内数据按Key值升序，并不是物理排序，插入时只找可用空间放，一个记录存另一个记录的页内offset。
因为一页的大小被限制到16KB（16384字节），但是一个字段的长度不能超过65535字节。所以这里会产生一个行溢出的问题，所以里面处理的方式，在不同格式下会有些差异。大体上就是将超出的部分放在别的页里面。原本的列里面保存的是别的页上面的地址。
#### 其它
看来来，比rocketmq的内存映射文件处理复杂，比固定索引文件长度的复杂太多了，这只是存储方面。所以存binlog，redo，undo等日志和内存中处理就快多了，还有checkpoint确认日志中的写入数据文件，如果都等复杂的文件存储处理完就慢了。
不过从更大的层面，也有相似性，也有客户端管理，权限，请求处理，事务等，也许hash索引更相似。后面提到mongodb的mmap存储引擎也用了内存映射文件处理。
#### 参考
http://mysql.taobao.org/monthly/2016/02/01/
https://dev.mysql.com/doc/refman/5.7/en/innodb-file-space.html
https://www.cnblogs.com/wcwen1990/p/6655386.html
https://www.jianshu.com/p/aab602b842c2
https://www.cnblogs.com/ijia/p/10739192.html
https://yq.aliyun.com/articles/51133
https://blog.51cto.com/59090939/1955122
## 二、mongodb的文件存储
为了能够更好的支持大数据或者实时应用，现在我们通常需要非关系型的、动态的schema，这样就没有必要进行表关联查询。它不再需要遵循 SQL 和关系型数据库的体系，可以更*对特定场景进行优化，而在 MongoDB 假设的场景中遍历数据并不是常见的需求，它追求的是读写单个记录的性能。
MongoDB 为于存bson文档数据，没有schema，理论上可以随便存不同结构的文档数据，它减少了一些关系数据库必要的限制，那就需要另外的存储方式提高读写速度了。它的id索引采用特殊的b-tree，不是关系数据库的b+tree，还有一个LSM 树不介绍了。关系数据库利用了b+树的叶子节点相连，在方便查询同时也非常方便遍历这个需求，但MongoDB 认为查询单个数据记录远比遍历数据的查询更加常见，但对于遍历数据也需要有相对较好的性能支持，所以用b树就行了。如果用hash，遍历就太差了。
它也有两个主要的存储引擎，分别是MMAPv1 和wiredTiger。这里介绍老的 MMAPv1 存储引擎的数据组织方式，虽然会被废弃，但资料比较多，方便学习，这时数据文件使用 mmap 映射到内存空间进行管理，内存的管理（哪些数据何时换入/换出）完全交给OS管理。两者的对比可以看参考。
### 1. 文件空间层次
MongoDB 在库之下的Collection与Document概念分别对应rdb中的table与row。存储层次分别为：库，Namespace（同一表数据，索引各不同ns），区（extent），record。
一个mongodb服务器上可以建多个库Database(DB) ，每个库（比如mydb名字的库）由一个.ns文件及若干个数据文件组成，数据文件从0开始编号，依次为mydb.0、mydb.1、mydb.2等，文件大小从64MB起，依次倍增，最大为2GB。不同库之间是文件隔离的，所以最高层次就是库，除了ns文件，只是切分扩展。
数据文件中有一个个的extent，它们可以属于不同的namespace，即一个新开辟的文件空间可以存库里的任何表数据。在ns中记录着同一个表的开始与结束的extent位置，同一个表的extent形成双向链表，这样就从表的角度串起了所有的extent。一个extent里都是同一个表的数据record。
> 房管局又给这些树型的企业人员造房子了，先造一个管理用房子，里面可能安排26715个人管理一个企业的管理人员线与普通员工线，分两个人分别管理这两条线。 > > extent就是一栋楼（方舱），连续的空间，里面没房间，直接到床位置。楼前记录第一个人与最后一个人位置。同一个楼里人与人也指针关联。 > > 数据编号文件就是一个个大的小区。人多就建新小区的新楼。 > > 一个公司的员工这条线，可以安排在不同小区的的不同楼里，但一个楼里都是一个公司的。公司的领导层，也安排在不同小区的不同楼里，一个楼里都是一个公司的。 > > 房管局的一个管理人，记录这个线上第一个楼与最后一个楼位置，线上的楼之间也连着。
### 2. 关联关系
上面已经提到了一部分，再明确一下。
一个namespace串起不同文件上的extent，一个extent里的记录也自己串起来。这样当对此collection进行scan操作时（比如全表扫描），可以提供很大的便利性。
每个数据文件包含一个固定长度头部DataFileHeader，Header 中包含数据文件版本、文件大小、未使用空间位置及长度、空闲 extent 链表起始及结束位置。extent被回收时，就会放到数据文件对应的空闲 extent 链表里。说明基本上都有链表来管理空间层次。
一个 namespace下的所有的已删除记录（可以回收并复用的存储空间）以单向链表的形式，为了最大化存储空间利用率，不同size（32B、64B、128B…）的记录被挂在不同的链表上，可以复用空间。这几个空闲链的头存在ns中的这个namespace中管理，记录着文件号与偏移位置。
新的记录插入到extent中，可能找空的地方，也可能顺序的插入，我猜测不管插到哪个extent中的哪个物理位置，都在这个extent中的record链接的最后。现在查到了源码如下：
```c++ //insert方法（pdfile.cpp 第1467行） Record * oldlast = e -> lastRecord.rec(); r -> prevOfs = e -> lastRecord.getOfs();//新记录的前指针，指向原来最后一个记录 r -> nextOfs = DiskLoc::NullOfs; ```
### 3. 索引的数据
The index namespace is a* **combination of the database name and the name of the collection or index***, like so: [database-name].[collection-or-index-name].*
官方文档写道MongoDB defines indexes at the collection level and they are supported by any field or embedded field of the documents in the collection.（索引定义在collection的层级，可建在任何字段或者嵌入的字段上）
每一个索引也对应于一个namespace ,如db.coll 这个collection的索引{x:1,y:1},其索引保存到了namespace :
db.coll.$x_1_y_1。
这里有b树构建源码解读：http://www.itboth.com/d/ZfMNRb/system-sharding-mongodb-insert 由于mmap，产生的Every b-tree bucket is allocated as needed and thus has it's own location within the data file. **但具体的信息没找到足够细节相关的资料，C++又不懂。英文网页有一点点信息**
https://dba.stackexchange.com/questions/65180/ （how-are-mongodb-indexes-stored-on-disk）中提到：
```html
there is a logical structure within the files, extents, that are the real units of storage. That and far more is covered in detail by [this presentation](http://www.mongodb.com/presentations/storage-engine-internals) by Mathias Stearn - one of the kernel developers at MongoDB.
Indexes are just another (structured) form of data in MongoDB and they are stored in linked extents throughout the file.
（数据文件中的extents是真实存在的存储单元，索引也是在整个文件所链接着的extent中存储的。）索引的结构估计就是BtreeBucket。
```
刚找到这个：http://zhangliyong.github.io/posts/2014/02/19/mongodb-index-internals.html
```html //These buckets are of size BucketSize and their body is an ordered array of pairs, where disk loc is the disk location of a document and bson key is a projection of this document into the schema of the index for this btree. Ordering is determined on the basis of bson key first and then disk loc in case of a tie. All bson keys for a btree have identical schemas with empty string field names and may not have an objsize() exceeding KeyMax. The btree's buckets are themselves organized into an ordered tree. //When the btree is serialized on the disk, every bucket is stored as a record, like a document in a collection. Each bucket has a fixed size 8192, but with 16 byte to store record header. (当btree存盘时，每个bucket作为一个record，象数据document一样。) ```
以上算是index的存储基本明白了。
### 4. 其它
文件空间还是按链表进行组织，按namespace有不同的条线串起来，条线上的数据又有数据的组织方式，比如数据条线的record在extent内小双向链表，索引条线又是另外的指针地址相连。还有空闲的也链表串起来，这点与mysql大体相似。
关于插入新record后遍历顺序，网上有人问https://*.com/questions/11599069/。查到sort如果没有指定，是按自然顺序，什么是自然顺序，一般是插入顺序。但会利用删除记录后的空闲空间，所以不是全局最后，而可能在其它extent中的最后记录后面。Capped Collections除外。
mongodb的索引很丰富，包括有TTL Indexes。可以设置多少时间后删除，也可以设置成未来要删除的时间，0秒后删除。
https://blog.csdn.net/u010385646/article/details/52493464（mmap方式介绍）
https://blog.csdn.net/tengxy_cloud/article/details/52808462
https://mongoing.com/archives/35143
http://www.mongoing.com/blog/file-storage
https://www.jb51.net/article/117764.htm
https://yq.aliyun.com/articles/11025 (源码元数据定义)
https://blog.csdn.net/n88Lpo/article/details/90276252
https://www.cnblogs.com/linguoguo/p/12291686.html
https://www.jb51.net/article/65634.htm
## 三、Hbase
HBase – Hadoop Database，是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统，利用HBase技术可在廉价PC Server上搭建起大规模结构化存储集群。hbase是建立在hdfs上的数据库，面向列。id是保证全局顺序的。分布在region中，数据多了会分裂region。
id设计很有讲究，不能局部过热写入，还能按id范围查找。
#### 1. 逻辑层次
一个比较大的不同时，一个hfile文件对应最小的层次。而mysql中，一个文件对应一个表空间。mongodb中，几个切分的文件拼起来，对应一个库。那么问题来了，其实层次的内容，包含关系存在哪？
1. Region
table在行的方向上分隔为多个Region。Region是HBase中分布式存储和负载均衡的最小单元，即不同的region可以分别在不同的Region Server上，但同一个Region是不会拆分到多个server上。Region按大小分隔，表中每一行只能属于一个region。随着数据不断插入表，region不断增大，当region的某个列族达到一个阈值（默认256M）时就会分成两个新的region。每个HStore对应了Table中的一个column family的存储，可以看出每个columnfamily其实就是一个集中的存储单元，因此最好将具备共同IO特性的column放在一个column family中，这样最高效。
2. Store
每一个region有一个或多个store组成，至少是一个store，hbase会把一起访问的数据放在一个store里面，即为每个ColumnFamily建一个store（即有几个ColumnFamily，也就有几个Store）。一个Store由一个memStore和0或多个StoreFile组成。MemStore是 Sorted Memory Buffer，用户写入的数据首先会放入MemStore，当MemStore满了以后会Flush成一个StoreFile（底层实现是HFile）。HBase以store的大小来判断是否需要切分region。
3. MemStore
memStore 是放在内存里的。保存修改的数据即keyValues。当memStore的大小达到一个阀值（默认64MB）时，memStore会被flush到文件，即生成一个快照。目前hbase 会有一个线程来负责memStore的flush操作。
4. StoreFile
memStore内存中的数据写到文件后就是StoreFile（即memstore的每次flush操作都会生成一个新的StoreFile），StoreFile底层是以HFile的格式保存。
5. HFile
HFile是HBase中KeyValue数据的存储格式，是hadoop的二进制格式文件。一个StoreFile对应着一个HFile。而HFile是存储在HDFS之上的。HFile文件格式是基于Google Bigtable中的SSTable。
首先HFile文件是不定长的，长度固定的只有其中的两块：Trailer和FileInfo。Trailer中又指针指向其他数据块的起始点，FileInfo记录了文件的一些meta信息。
由于是分布式系统，Region是HBase中分布式存储和负载均衡的最小单元，也就是Region（一个表的一部分排序的记录），可以在RegionServer机器间移动。
> 房管局又来分房子了，可以对比一下： > > 房管局住在Hmaster上，管理的信息在zookeeper上了，相对简单了。现在只关注给很多公司（table）的人员分房子。没有小区的概念，直接就分楼，每栋楼里都是同一公司的员工，比如按年龄排着号。 > > region相当于楼，一个公司有哪些楼在zk上有。公司按部门分配楼里的单元。每个单元一楼临时人员房（内存），上面是固定房。一个固定房主是一个hfile。当然人数不同，房间大小不同。 > > 一个公司的新招的人由于按年纪要全局排序，可能插在某个楼里的人员里。一个楼的人太多了，就分成两个楼了。 > > 公司在不同的区域被分配楼，可以按楼进行搬迁，达到区域间人分布的平衡。
#### 2. 数据持久化
用到Memstore最主要的原因是：存储在HDFS上的数据需要按照row key 排序。而HDFS本身被设计为顺序读写(sequential reads/writes)，不允许修改。这样的话，HBase就不能够高效的写数据，因为要写入到HBase的数据不会被排序，这也就意味着没有为将来的检索优化。为了解决这个问题，HBase将最近接收到的数据缓存在内存中(in Memstore)，在持久化到HDFS之前完成排序，然后再快速的顺序写入HDFS。
数据是排序的，每个region内的数据的key最小值与最大值范围是有记录的。zk上应该有记录meta数据的。
https://www.cnblogs.com/163yun/p/9020629.html（hfile格式）
HBase中定义了8种BlockType，每种BlockType对应的block都存储不同的数据内容，有的存储用户数据，有的存储索引数据，有的存储meta元数据。对于任意一种类型的HFileBlock， 都拥有相同结构的BlockHeader ， 但是BlockData结构却不相同。
#### 3. 数据操作定位
Client端想要插入，删除，查询数据都需要先找到相应的RegionServer。很多文章从zk的meta数据进行了说明，包括三层与新的二层查找。但我有疑问，找到了regionserver后，它又怎么定位对数据进行操作呢？这个没的找到答案，单机的系统可以找文件，找区，找偏移量，但这个情况下呢？但我想到了regionserver可以宕机，看来它只管按hdfs来读写数据就行了。它本身不会存任何自己独有的管理信息。
https://www.cnblogs.com/zwgblog/p/5733583.html (meta表)
https://jingyan.baidu.com/article/7c6fb42832124a80642c90f4.html（regionserver宕机）
#### 4. 数据模型操作
数据模型的四个主要操作是Get，Put，Scan和Delete。可以通过Table实例进行操作。HBase是否支持join是一个常见的问题，答案是没有，至少没办法像RDBMS那样支持。
https://zhuanlan.zhihu.com/p/47074785（优化的目标与办法）
rowkey的比较规则是整个HBase数据模型的核心，直接影响了整个请求路由体系的设计、读写链路、rowkey设计、scan的使用等，贯穿整个HBase。对于用户而言，深入理解这个规则及其应用有助于做出良好的表设计，写出精准、高效的scan。
当大量请求访问HBase集群的一个或少数几个节点，造成少数RegionServer的读写请求过多、负载过大，而其他RegionServer负载却很小，这样就造成**热点现象**。大量访问会使热点Region所在的主机负载过大，引起性能下降，甚至导致Region不可用。所以我们在向HBase中插入数据的时候，应尽量均衡地把记录分散到不同的Region里去，平衡每个Region的压力。
RowKey经验：https://zhuanlan.zhihu.com/p/69462736
- 1. 结合业务场景特点，选择合适的字段来做为RowKey，并且按照查询频次来放置字段顺序
- 2. 通过设计的RowKey能尽可能的将数据打散到整个集群中，均衡负载，避免热点问题
- 3. 设计的RowKey应尽量简短
> 示例：比如需要保存一个用户的操作记录，按照操作时间倒序排序，在设计rowkey的时候，可以这样设计 > [userId反转][Long.Max_Value - timestamp]，在查询用户的所有操作记录数据的时候，直接指定反转后的userId，startRow是[userId反转][000000000000],stopRow是[userId反转][Long.Max_Value - timestamp] > 如果需要查询某段时间的操作记录，startRow是[user反转][Long.Max_Value - 起始时间]，stopRow是[userId反转][Long.Max_Value - 结束时间]
#### 5. 其它
一个表的列族不能太多，一般一个。由于列簇共享region，由于关联性在分裂与flush时影响导致性能下降。都是廉价机集群，性能是靠分担才上去的。
#### 6. 参考：
https://www.cnblogs.com/simple-focus/p/6198329.html
https://blog.csdn.net/lijingjingchn/article/details/89924181
https://blog.csdn.net/xiaoshunzi111/article/details/69844526
待补充...
## 四、lucene---ElasticSearch
lucene作为全文检索工具，数据的保存也很非常有特色的，实际上也是非常复杂的，本文只汇总整体关系，从我们要存什么开始。而多数文章是使用，或者讲述倒排表和高效的词典的FST查找之类的方面，讲总体的不多，可能是比较简单？首先用一个Lucene多字段不同Analyzer分词器的索引的创建和查询例子，来引出设计上的特点。
#### 1. 引出业务概念与数据层次
问题来源于：https://bbs.csdn.net/topics/391841943，虽然楼主开始的用法不对，却也说明了几个数据关系。
IndexWriter负责把一个文档进行索引并写入一个文件夹目录。目前先在这个层次内进行说明。一个索引文件的目录，由一个IndexWriter把一类的Document写进去。这个层次类似于数据库表这个层次的概念。
Document由一到多个Field组成，类似于字段，每个字段有名字与值，可以选择是否进行保存，是否进行分词等，而且可以设置不同的字段用不同的分词器。
原文作者不知道PerFieldAnalyzerWrapper，可用于同一类型Document的各字段分词。而是分成多个不同的Document，这个层面用不同的分词器，最后想用MultiReader垮文档组合读，而QueryParser解析用户查询输入词，这又不可能按Document不同进行不同的分词切分（因为作者在更细的层级实现了不同切分），所以搞不下去了。
所以，在一种Document这个层面，要存储的东西有：
**原始数据：**
这种Document的每一个Document的有字段的原始数据，可能要保存。有时候使用时，可只保存一个id，其它原始数据存在其它数据库里。存的方式有正向文件（行式存储且多文档一起压缩），列式存储两种。前者适合展示倒排查到的文档，后者可对检索结果进行分类、排序、数学计算等聚合操作。
**倒排表**：
字段可以进行不同分词器的分词后，建倒排表。表明一个词，出现在哪些文件的这个字段数据的什么位置及次数之类的。每一个要建索引的字段都产生一个倒排表。这类Document多个字段有索引，就产生多个倒排表。
#### 2. 倒排表存储方式
还是限于一种Document，即一个文件目录，一个IndexWriter的级别。首先发现就是文档类型太多了。
一个字段所建的倒排表，是所出现的一堆的词与每个词在哪些文档及位置的关系表。词要存，之间的关系要存。lucene用了几个不不同后缀的文件，拆成三个层级来存。
- - .tip：一堆排序的词怎么个存，又怎么找？数组，hash，tree，跳跃表？作者用了FST（有限状态机），把词还分成了前缀与后缀，内存里只加载很小的前缀部分数据，前缀按字节关联着。tip就存前缀与指向后缀.tim的指针。
- - .tim：这里就存后缀的数据，及指向.doc中倒排数据的指针。
- - .doc：这里就完全存一个词后缀，它在哪些个文档id中，id就是数字，一推数字。id这些数字怎么存也有讲究。id有顺序就按增量存，而增量数字不大，就给不同长度的字节来放。压缩到极致了。另有.pay与.pox文件，分别是词频、Payload信息、pox是记录位置信息。
照这个思想，其实hash方式也可以拆开，hash部分一个文件，冲突链表一个文件，内存只加载前面一个也可以小很多了。另外要提的是，不可能所有的Document放一起，它还有一个维度要segement段的概念，段会合并，相应的倒排表也会合并。这个维度在前面提到的数据库中也有，比如hbase的region，比如monodb中的extent。Segment上每个字段都有自己的一个FST（FSTIndex）记录在`.tip`上，所以也只是同一字段的合并FST，不同字段还是分开的。不过都放在一个文件上。具体文件怎么划空间就不细看了，无法研究那么透彻。
一个倒排表就存了这么多信息，所以它的检索过程分为三个步骤：
- 1. 内存加载tip文件，通过FST匹配前缀找到后缀词块位置。
- 2. 根据词块位置，读取磁盘中tim文件中后缀块并找到后缀和相应的倒排表位置信息。
- 3. 根据倒排表位置去doc文件中加载倒排表。
#### 3. 原始数据存储方式
##### **正向文件存储**
Lucene对原始文档也提供了存储功能，存放是**行式存储**，并且为了提高空间利用率，是多文档一起压缩。它存储特点就是分块+压缩。fdt文件就是存放原始文档的文件，它占了索引库90%的磁盘空间，fdx文件为索引文件，通过文档号（自增数字）快速得到文档位置，它们的文件结构如下：
- - .fnm中为元信息存放了各列类型、列名、存储方式等信息。
- - .fdt为文档值，里面一个chunk就是一个块，Lucene索引文档时，先缓存文档，缓存大于16KB时，就会把文档压缩存储。一个chunk包含了该chunk起始文档、多少个文档、压缩后的文档内容。
- - .fdx为文档号索引，之前的倒排表存放的时文档号，再通过fdx才能快速定位到文档位置即chunk位置，它的索引结构比较简单，就是跳跃表结构，首先它会把1024个chunk归为一个block,每个block记载了起始文档值，block就相当于一级跳表。
既然多文档压缩分块了，所以就要从文档号到文档位置的索引，所以查找文档，就分为三步：
第一步二分查找block，定位属于哪个block。
第二步就是根据从block里根据每个chunk的起始文档号，找到属于哪个chunk和chunk位置。
第三步就是去加载fdt的chunk，找到文档。
##### 列式存储DocValues
需要对检索结果进行分类、排序、数学计算等聚合操作时需要文档号到值的快速映射，而原先不管是倒排索引还是行式存储的文档都无法满足要求。比如有个部门字段没有分词，但建了索引，所以有倒排表，可以按部门名称找出相关的文档，对其中的一些字段进行聚合运算。
**在我看来，这就是抢数据库的饭碗，为何不把原始数据存储放其它类型的数据库中，发挥各自强项呢？这个只查出id就可以了。如果原始数据中还想有关联检索，是否lucene也考虑增加功能呢？**还是说说结构吧：
4.0版本后Lucene推出了DocValues来解决这一问题，它和FieldCache一样，都为列式存储，但它有如下优点：
- 1. 预先构建，写入文件。
- 2. 基于映射文件来做，脱离JVM堆内存，系统调度缺页。
DocValues这种实现方法只比内存FieldCache慢大概10~25%，但稳定性却得到了极大提升。
Lucene目前有五种类型的DocValues：NUMERIC、BINARY、SORTED、SORTED_SET、SORTED_NUMERIC，针对每种类型Lucene都有特定的压缩方法。
对DocValues的应用，ElasticSearch功能实现地更系统、更完整，即ElasticSearch的Aggregations——聚合功能。
#### 4. Elasticsearch
Elasticsearch 是一个分布式可扩展的实时搜索和分析引擎,一个建立在全文搜索引擎 Apache Lucene(TM) 基础上的搜索引擎。特点是：
- - Engine：屏蔽 Lucene 操作细节的抽象层
- - Http：对外提供 restful api，让不同开发语言的应用都可以接入
- - 分布式：分片与副本，选master，状态等功能，以文档id作为分片依据，分了就还有聚合的很多功能。
其实有特色的全文检索东西都在lucene中，这里只写一点，有这样一个所谓比较：
``` 关系数据库 ⇒ 数据库 ⇒ 表 ⇒ 行 ⇒ 列(Columns) Elasticsearch ⇒ 索引(Index) ⇒ 类型(type) ⇒ 文档(Docments) ⇒ 字段(Fields) ```
其实我感觉不准确，前面讲lucene时，我把一种Docments当成一个表的。这里的tye这个层次怎么理解呢？我认为是抽象类与多个具体类这样的关系，具体实现与存储上的问题暂不分析了，除非真正了解这么深。
**type的使用**
一个例子就清楚了。比如商品index，里面存放了所有的商品数据，商品document
但是商品分很多种类，每个种类的document的field可能不太一样，比如说电器商品，可能还包含一些诸如售后时间范围这样的特殊field；生鲜商品，还包含一些诸如生鲜保质期之类的特殊field
type，日化商品type，电器商品type，生鲜商品type 日化商品type：product_id，product_name，product_desc，category_id，category_name 电器商品type：product_id，product_name，product_desc，category_id，category_name，service_period 生鲜商品type：product_id，product_name，product_desc，category_id，category_name，eat_period
不同 type 里的字段需要保持一致。例如，一个 index 下的不同 type 里有两个名字相同的字段，他们的类型（string, date 等等）和配置也必须相同。这难道认为是表的概念吗？除非理解为1对1的公共字段与非公共字段的一组相关表。
只在某个 type 里存在的字段，在其他没有该字段的 type 中也会消耗资源。这是 Lucene Index 带来的常见问题：它不喜欢稀疏。由于连续文档之间的差异太大，稀疏的 posting list 的压缩效率不高。这个问题在 doc value 上更为严重：为了提高速度，doc value 通常会为每个文档预留一个固定大小的空间，以便文档可以被高速检索。这意味着，如果 Lucene 确定它需要一个字节来存储某个数字类型的字段，它同样会给没有这个字段的文档预留一个字节。未来版本的 ES 会在这方面做一些改进，但是我仍然建议你在建模的时候尽量避免稀疏。
https://blog.csdn.net/zteny/article/details/82857080
https://blog.csdn.net/njpjsoftdev/article/details/54015485
https://baijiahao.baidu.com/s?id=1666739392937388743&wfr=spider&for=pc
https://www.jianshu.com/p/044d4b1adc89
## 五、redis
redis作为内存数据库，就只从编程语言的角度说说内存中的数据结构，至于快照存盘设计有空再补充。
redis用C语言写的，有五大数据结构，但底层是怎样的数据结构呢，他们和我们java中的HashMap、List、等使用的数据结构有什么区别呢？
### 1. 基本数据结构
- 字符串处理(string)：Redis自己构建了一种名叫`Simple dynamic string(SDS)`的数据结构，包含字节数组，已用字节与空闲字节，目的是预分配，不担心溢出。
- 链表：在双向链表上扩展了头、尾节点、元素数等属性
- Redis的Hash：就是在`数组+链表`的基础上，进行了一些rehash优化等。
- 跳跃表：跳跃表比树简单，在redis中用在有序集合键、集群节点内部数据结构
- 整数集合(intset)：当一个结合中只包含整数元素，redis就会用这个来存储。根据数的大小，用不空的空间，节约内存。
- 压缩列表(ziplist)：ziplist是redis为了节约内存而开发的顺序型数据结构。它被用在列表键和哈希键中。一般用于小数据存储。
- 快速列表(quicklist)：一个由ziplist组成的双向链表，一个quicklist可以有多个quicklist节点，用在列表的底层实现。
当看到ziplist被封装在quicklistNode中，再增加一些管理数据并串起链表，有点象包装第三方的对象增加属性的类。大链接里的小数组，又联想到前面extent中的page这样的大链接里面小链接的形式，也是一种分层架构思想的体现。
### 2. 对应关系
多种实现是因为有使用条件，条件上的一些阈值可以修改。
参考：
https://zhuanlan.zhihu.com/p/71057875
https://www.cnblogs.com/javazhiyin/p/11063944.html
## 六、rocketmq
消息是顺序写文件的，这样很快，而【消息信息】要分队列存放供消费，还要索引来快速拿到消息，所以有独立的线程从原始消息文件来建消息索引与各个队列。索引文件由头+多个hashslot+多个消息数据块组成（40byte+?*4+*?20）。类似hashmap方式。
### 1. 索引主要类与核心操作
#### IndexHeader类
每个索引文件有40个byte的头，包括开始结束时间各8个，开始结束物理位置各8个，hashslot数与包含的索引数是整数，4个byte，共4*8+4+4=40个byte。
只需要从对应文件映射出来mappedByteBuffer，并slice出的一个byteBuffer来操作。用put/get指定位置的long/int就设/取值了。slice是自己的位置，但与相同的操作对象。
IndexHeader类，有这些属性，又持有byteBuffer，就可以初始化对象时加载文件中的值，也可以操作中设置新值到文件中。
#### IndexFile类
它持有mappedFile类，以及这个类的FileChannel与mappedByteBuffer，这里是引用，也可以当成是继承吧，反正核心的东西我直接持有了。
建一个新的IndexFile，等于新建一个以offset为名字的可读写的文件并映射内存mappedByteBuffer。前面讲这个类把mappedByteBuffer slice了一下，等于一部分交给IndexHeader来管理了。剩下的部分自己来管理。看看它的两个主要操作：
#### 建索引
putKey(String, long, long)，参数：key 物理offset 时间
- - 按key对slotnum取模，找到放第几个slot，再根据头大小，每个slot大小，4byte，算出这个slot的物理位置
- - 先从里面取出之前的值，如果之前有值，先记着，否则0
- - 根据索引的个数与索引的大小，加上前面的头与所有slot的占用，得到记录索引的地方，就是后面顺序写入
- - 先写int，再long，再2个int就是4.8.4.4个byte，最后一个int记录前面slot里的值，就是前一个相同hash的索引是当时的第几个。就之前一个是整个文件的第几个，都顺序记录的。
#### 取值
selectPhyOffset(List<Long>, String, int, long, long, boolean)
- - key的hash值对slot数取模，并拿出这个slot中的值int，表示数据是整个文件第几个消息。
- - 从头+全部slot+消息索引大小*位置，得到数据位置。
- - 按位置从中取出4.8.4.4 byte，分别是key,消息物理位置，时间，上一同hash的消息是第几个。
- - 如果key相同，就是了，如不同，就在上一个消息的位置再取这几个值比较。
### 2. 特点说明
两个操作类，都持有mappedByteBuffer，分别操作不同部分。分工明确。
写索引时，在slot位置记录自己排号，就是第几个，不是具体offset位置，这样数字比较小，offset可以计算出来。如果有冲突，新写的占用slot，但后面数据中有4byte有记录前一个的排号。如果按hash找出来，但key不对，就拿出前一个排号再查key对不对，这样直到找到。算是链表方式。
除了生成索引，还要生成队列，按topic与queueId产生一组文件，由ConsumeQueue类管理
- - 新产生的消息，要放进相应的队列里相关【消息信息】
- - 先new一个byteBuffer，写入【消息位置/大小/标签码】
- - 从队列总offset与一个【消息信息】大小，算出在哪个具体文件中记录。
- - 在这个文件中，追加byteBuffer，是用fileChannel.write来做的。