多维度谈OLAP与OLTP数据库

OLAP与OLTP介绍

OLAP(OnLine Analytical Processing)

Online analytical processing (OLAP) is a system for performing multi-dimensional analysis at high speeds on large volumes of data. Typically, this data is from adata warehouse, data mart or some other centralized data store. OLAP is ideal fordata mining, business intelligence and complex analytical calculations, as well as business reporting functions like financial analysis, budgeting and sales forecasting.

引用IBM博客上的一段话就是：

在线分析处理（OLAP）是一种用于对大量数据进行高速多维分析的系统。 通常，此数据来自数据仓库，数据集市或某些其他集中式数据存储。 OLAP是数据挖掘，商业智能和复杂分析计算以及诸如财务分析，预算和销售预测之类的业务报告功能的理想选择。所以OLAP重分析、重决策，数据量大因此需支持高吞吐；对数据多维度分析可能涉及复杂查询，需要能够对多维数据进行钻取、切片切块、旋转。

OLTP(OnLine Transaction Processing)

Online transactional processing (OLTP)enables the real-time execution of large numbers of database transactions by large numbers of people, typically over the Internet. OLTP systems are behind many of our everyday transactions, from ATMs to in-store purchases to hotel reservations. OLTP can also drive non-financial transactions, including password changes and text messages.

在线事务处理（OLTP）使大量人员通常通过Internet实时执行大量数据库事务。 例如 从ATM机到店内购买再到酒店预订，OLTP系统是我们日常交易的基础。 OLTP还可以推动非金融交易，包括密码更改和短信。所以OLTP要求支持事务查询、低延迟、数据实时性、可靠性要求高。

参考：https://www.ibm.com/cloud/blog/olap-vs-oltp

从底层结构上(B/B+树 LSM树)谈

熟悉数据结构的同学都知道，BST平衡树(红黑树 & AVL树)数据查询速度快(logN)，BST平衡树单个父节点的字节点数量小于等于2，高度为h的平衡树，节点数N最多为2^h-1。基于内存的的BST平衡树存储结构在高度不断增加时对插入查询性能影响不大，但是基于磁盘存储时，鉴于磁盘寻道时间成本，随着树高度增加，数据查询时间将层指数被放大。例如磁盘单次寻道时间为10ms，百万级别的数据耗时约 10 * 20ms = 0.2s，当数据上亿级别，耗时将扩大至2s。

-----------------------------支持多节点的B树数据结构衍生而出----------------------------

B树

B树结构如下，草图勿怪，表明其意即可

m = 3的B树

参考维基百科，根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：

1. 每一个节点最多有 m 个子节点
2. 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
3. 如果根节点不是叶子节点，那么它至少有两个子节点
4. 有 k 个子节点的非叶子节点拥有 k − 1 个键
5. 所有的叶子节点都在同一层

每一个内部节点的键将节点的子树分开。例如，如果一个内部节点有3个子节点（子树），那么它就必须有两个键： a1 和 a2 。左边子树的所有值都必须小于 a1 ，中间子树的所有值都必须在 a1 和a2 之间，右边子树的所有值都必须大于 a2 。

内部节点

• 内部节点是除叶子节点和根节点之外的所有节点。它们通常被表示为一组有序的元素和指向子节点的指针。每一个内部节点拥有最多U个，最少L个子节点。
• 元素的数量总是比子节点指针的数量少一（元素的数量在L-1 和U-1 之间）。U必须等于 2L或者 2L-1;因此，每一个内部节点都至少是半满的。U和L之间的关系意味着两个半满的节点可以合并成一个合法的节点，一个全满的节点可以被分裂成两个合法的节点（如果父节点有空间容纳移来的一个元素）。
• 这些特性使得在B树中删除或插入新的值时可以调整树来保持B树的性质。

根节点

• 根节点拥有的子节点数量的上限和内部节点相同，但是没有下限。例如，当整个树中的元素数量小于L-1 时，根节点是唯一的节点并且没有任何子节点。

叶子节点

• 叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。
• 一个深度为n+1 的B树可以容纳的元素数量大约是深度为 n 的B树的 U 倍，但是搜索、插入和删除操作的开销也会增加。和其他的平衡树一样，这一开销增加的速度远远慢于元素数量的增加。
• 一些平衡树只在叶子节点中存储值，而且叶子节点和内部节点使用不同的结构。B树在每一个节点中都存储值，所有的节点有着相同的结构。然而，因为叶子节点没有子节点，所以可以通过使用专门的结构来提高B树的性能。

B树详细介绍可参考维基百科：https://zh.wikipedia.org/wiki/B%E6%A0%91

缺点

虽然多节点的B树降低了磁盘寻道的成本，但是B树结构在范围查询时存在劣势，这就衍生出B+树数据结构

----------------------支持多节点&范围查询的B+树数据结构衍生而出--------------------------

B+树

B树结构如下

该图是参考维基百科的，图示看出，叶子结点通过指针连接，这种存储结构大大利于顺序的范围查询；

规则

• B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
• B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
• B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
• 非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

特点

• B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
• B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
• B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
• B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
• B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B+树详细介绍可参考维基百科：https://zh.wikipedia.org/wiki/B%2B%E6%A0%91

缺点

为了引出LSM树，下面来说下磁盘的结构划分

磁盘扇区，磁盘块，磁盘页的区别：

扇区：磁盘的最小存储单位；

磁盘块：文件系统读写数据的最小单位；

页：内存的最小存储单位；

磁盘块和页的大小一般情况下为4KB，所以在B+树中一个节点的最大存储数据个数的总大小一般不能超过4KB，针对大规模写操作，B+树需要不停的分列合并以平衡其结构，且每次操作均会涉及磁盘寻道；所以基于B+树的MYSQL在数据量大时需要分库分表

适用场景

基于B+树结构的存储具有很好的读性能和范围查询，确定是承载数量大时需要做其他策略(例如Mysql的分库分表)以适应业务需求，因此基于B+树的存储结构比较适用于OLTP应用场景；例如 MySQL 作为 OLTP 数据库不仅具备事务的处理能力，而且保证数据的持久化并且能够有一定的实时数据查询能力。

-----------------------支持高效批量写操作的LSM树数据结构衍生而出--------------------------

LSM树

LSM树的结构如下所示，LSM存储结构主要分为两部分：基于存储的Memtable和基于磁盘的SSTable文件。

LSM树

Memtable

根据key值顺序存储<key,value>，基于内存的存储断电后会失效，通过WAL Log(Write-ahead logging，预写式日志)方式保障数据可靠性，机器故障时通过WAL恢复历史内存数据，当Memtable写满时，内存出现会Flush或Compation至磁盘；

Immutable MemTable

当 MemTable达到一定大小后，会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。

SSTable(Sorted String Table)

有序<key, value>集合，是LSM树组在磁盘中的数据结构。为了加快SSTable的读取，可以通过建立key的索引以及布隆过滤器来加快key的查找。途中Level 0 空间占满后即触发Major Compaction，合并Level 0数据至Level 1，其他层同理。

缺点

多级顺序存储这会引发两个问题：

• 大量的Major Compaction需要占用大量的CPU和磁盘IO，所以当数据达到一定量级后，必然会引起性能断崖式下跌；
• 删除不支持事务操作，尤其是批量Range的删除会很麻烦，可以参考RocksDB的Range删除，基本处理逻辑就是先在内存中标注需要删除的key(即墓碑标记，更新是新记录一条的数据)，待Majion Compaction时再依次同步至disk，所以批量删除不会立马释放磁盘存储空间。

适用场景

基于内存和基于磁盘均存储有序键值对，通过利用磁盘顺序写性能大大优于磁盘随机写性能来提高批量写，反之，顺序键值对存储结构一定程度上折损了读性能，尤其是存储在Level N中的数据；因此基于LSM树的数据库适用于写多读少的场景，例如OLAP应用场景。

从存储方式(行存储&列存储)谈

行存储和列存储

行存储

从上图黄色线部分可以看出行存储就是依照现有的(RowID,Date/Time,Meterial,CustomerName,Quantity)数据协议整行存储，存储完RowID=1的所有数据后依次存储下一行，典型的Mysql，SQL SERVER 等均采用行存储格式。

列存储

从上图绿色部分可以看出列式存储按照某一列纵向存储，例如先存储途中RowID(1,2,3,4,5,6,7)在存储Date/Time(845,861......)，列式存储的存在是针对对列进行操作(eg 对列聚类，求和等)可减少对全表的扫描。且列式存储同一列上的数据类型相同，便于压缩。

综上列存储的数据库更适合OLAP，行存储的数据库更适合OLTP