存储的数据结构
哈希索引
对于Key-Value的数据来说，hashTable是非常常见的索引方式，很适合更新频繁的场景。Value映射到一个数据文件中的字节偏移量，以能在数据存储中找到对应位置。
如果哈希索引存储在日志中，为了避免占用太多的磁盘空间，当日志增长到指定大小后，则关闭当前日志文件并开启新的日志文件，旧的日志文件成为只读。日志文件中，相同键的记录只需要保留最新的值即可，因此可以做压缩（Compaction）。同时，多个日志文件之间也可以做合并（Merging），生成新的日志文件。压缩和合并的工作可以在后台线程中完成，在工作完成之前，这些旧文件仍然可以提供查询，直到新文件生成并删除旧文件。
但是哈希索引也存在着某些局限性：
- 哈希表必须能放进内存，且会产生hash冲突
- 无法进行范围查询
SSTable / LSM Tree
如果要求键的顺序完全有序，则变成了SSTable（Sorted String Table），并要求每个键在SSTable中只出现一次。相比于HashTable，有如下几点优势：
- 由于键是有序的，因此Merge的过程更加简单和高效。利用归并排序（这样就不受内存大小的限制了），就可以保证多个SSTable的合并结果仍然是一个SSTable。当多个SSTable中出现相同的键时，只需要保留最新的值。
- 索引会变得更加稀疏，在一个SSTable中，只需要在索引中保存Block的第一个Key，这样在查找的时候，只需要先定位到Block，然后在block中顺序寻找即可。
- 在写入磁盘之前，就可以对Block中的记录进行压缩，从而减少IO。
SSTable的生成与维护
- 在内存中维护一个有序的数据结构，比如红黑树。这个内存树也被称为memtable
- 当memtable的大小超过阈值（几MB）时，写入到磁盘成为SSTable。写入成功后，继续在内存中产生新的memtable
- 当提供查询时，优先查询memtable，再查找最新的SSTable
- 后台线程会定期执行Compaction和Merge
LevelDb / RocksDb / HBase
LevelDb的生成过程
- memtable会生成Log File，默认超过4MB就会生成Sorted Table
- Sorted Table中存储的值，要么是key-value，要么是deletion marker，以便后续在compaction的时候删除记录
- 刚生成的Sorted Table又称为level-0，当level-0个数超过一定阈值后，会和level-1的文件进行合并，从而生成新的level-1文件
- level-0的文件之间可能存在重叠，其他层的文件不会重叠。当L层的总大小超过10^LMB，则需要进行合并生成新的L+1层
- 当进行合并时，一个L层的文件和L+1层有重叠的文件作为输入，生成新的L+1层。如果是0层，则会用多个文件作为输入，因为level-0文件之间会有重叠
HBase的compaction过程和LevelDB有所不同，更新和更小的SSTables先后被合并到更老的和更大的SSTable中。
B-Tree
B-Tree和LSM-Tree同样是键保证有序，但是B-Tree是将按照固定大小的Page进行存储，每次读取和写入都是以页面作为单位。这样设计更接近底层硬件。
一个页面作为根，页面之间存在引用关系，从而形成一棵树。每个子页面负责一段连续范围的键，叶子页面会存储键实际的值。
如果更新键的值，则需要定位到包含该键的叶子页面，更新该页的值，并重新写回磁盘。如果新增一个键，页面空间不足则会发生页面分裂，需要更新父页面的引用。
LSM-Tree VS B-Tree
| LSM-Tree | B-Tree | |
|---|---|---|
| 优势场景 | 写入性能较好 | 读取性能较好 |
| 写入吞吐 | 写入的SSTable比较紧凑，因此有更高的写入吞吐量 | 每次都要读取并更新写入整个页面，导致写放大 |
| 存储空间 | LSM-Tree支持压缩，且定期的Compaction以去除碎片 | 由于页面分割，导致一些空间未被使用 |
| 读取性能 | Compaction的过程会干扰正在进行的读写。且如果写入量过大，导致文件没有来得及合并，导致读取的路径较长 | 读取性能非常稳定 |
| 事务支持 | 每个键会有多个副本 | 每个键只存在于索引的一个位置中，在键上加锁可以实现事务隔离 |
其他索引
- 聚簇索引（Clustered Index）
- 覆盖索引（Covering Index）
- 多列索引（Concatenated Index）
- 多维索引（Multi-dimensional Index）
- 全文搜索和模糊索引
事务处理 vs 分析
OLTP or OLAP
| 属性 | OLTP | OLAP |
|---|---|---|
| 主要读取模式 | 少量查询，按索引查询 | 大数据量上的聚合 |
| 主要写入模式 | 随机写入，要求低延迟 | 批量导入（ETL）或事件流 |
| 主要用户 | 终端用户或消费者，web访问 | 内部分析师用于决策支持 |
| 处理的数据 | 数据的当前状态 | 随时间变化的历史数据 |
| 数据集大小 | GB ~ TB | TB ~ PB |
数据仓库
一个公司会有很多独立的业务系统，为了分析人员能够方便访问其中的数据，且不影响线上业务，需要有一个中心化的数据仓库，来存储各个业务系统的只读副本。将数据导入数据仓库的过程被称为抽取-转换-加载（Extract – Transform – Load，有时也会是ELT）。上文中讨论的存储数据结构，只适用于OLTP系统，对于分析查询来说，需要有特殊的存储结构。
星型模式和雪花模式
星型模式也被称为维度建模，在模式的中心是一张事实表，其中每一行代表着特定时间发生的具体事件。事实表会和一些维度表发生关联，这些维度代表了事实发生的时间、地点、方式等。这个模式的变体，又被称为雪花模式，关联维度被分解为了更多的维度。它被星型模式更加规范，但是使用起来可能更加困难。
列存储
数据仓库查询，一般只会用到其中的几列。如果是以行存储的话，读取过程将带来较大的浪费。面向列存储，是将每一列存储在一个单独文件中，从而节省读取成本。比如Parquet格式
列压缩
使用Bitmap可以有效地节省空间。如果一个列的基数比较少，总共有N个值，则可以转换为N个bitmap，每个bitmap记录该列哪些bit位上是有这个值的，有值记为1，无值记为0。再通过Run Length Encoding，则可以使列变得更加紧凑。
对于a = 1 and b = 30这样的查询，可以分别找到a=1、b=30这两个bitmap，然后计算bitand，可以快速筛选出符合的记录。
注：Cassandra和HBase中的Cluster，是将key和一行所有的列一起存储，并不使用列压缩。所以这两个仍然是面向行的。
列存储中的排序
在列存储中，如果不指定排序，则会按照行的插入顺序排序。但是也可以指定排序，需要注意的是，针对单独一个列排序是没有意义的，这样多列之间就没法找到同一行的数据了。
可以根据历史查询的经验，判断出列的排序顺序。比如订单表，将create_time作为第一排序字段，则相同创建时间的订单会放在一起，从而方便时间范围的查询。
另一个好处的话，就是排序列相同的值放在一起，那么Run Length Encoding压缩的效果会更好。
列存储的写入
如果底层是LSM-Tree的结构，那么列存储的写入就会比较方便。写操作先写入内存中的一个已排序的结构中，当积累了足够数据后，和磁盘上的列文件进行合并，然后写入新文件。