博客

摘要

本文主要对行式存储和列式存储原理做简单的分析，行式存储以mysql的Innodb 引擎和 Myisam 引擎为例，列式存储以parquet为例，最后对各自的优劣势总结。

一 总览

1. 特点

如图，行式存储以行位单位进行存储，列存储以列为单位进行存储。

2. 读写比较

写数据：

行存储的写入是一次完成。列存储由于需要把一行记录拆分成单列保存，写入次数明显比行存储多（意味着磁头调度次数多，而磁头调度是需要时间的，一般在1ms~10ms)，再加上磁头需要在盘片上移动和定位花费的时间，实际时间消耗会更大。所以，行存储在写入上占有很大的优势。

读数据：

行存储每次读取一行数据，可能存在冗余。列存储只会读取到需要的数据。

二 行式存储

为了加快查询，行式存储一般会建立索引。

1. B+树作为底层索引的优点

• 优秀检索速度，时间复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数；
• 尽可能少的磁盘 IO，加快了检索速度；
• 可以支持范围查找。

2. Innodb 引擎和 Myisam 引擎的实现

MyISAM 虽然数据查找性能极佳，但是不支持事务处理。Innodb 最大的特色就是支持了 ACID 兼容的事务功能，而且他支持行级锁。这两个引擎底层数据和索引的组织方式并不一样，MyISAM 引擎把数据和索引分开了，一人一个文件，这叫做非聚集索引方式；Innodb 引擎把数据和索引放在同一个文件里了，这叫做聚集索引方式。

MyISAM 引擎的底层实现（非聚集索引方式）

MyISAM 用的是非聚集索引方式，即数据和索引落在不同的两个文件上。MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

当我们为某个字段添加索引时，我们同样会生成对应字段的索引树，该字段的索引树的叶子节点同样是记录了对应数据的物理地址，然后也是拿着这个物理地址去数据文件里定位到具体的数据记录。

Innodb 引擎的底层实现

InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，如左下图所示，而 B+树的叶子节点存储的是主键 ID 对应的数据，比如在执行 select * from user_info where id=15 这个语句时，InnoDB 就会查询这颗主键 ID 索引 B+树，找到对应的 user_name=‘Bob’。

这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因。当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY。注意，叶子存储的是主键 KEY！拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

InnoDB 只在主键索引树的叶子节点存储了具体数据，但是其他索引树却不存具体数据，而要多此一举先找到主键，再在主键索引树找到对应的数据，原因就是为了节省空间。

三 列式存储

1. 背景

随着数据量的增加，大家开始寻找一种高效的数据格式，来解决存储与查询环节的痛点。

• 高效的压缩编码，用于降低存储成本
• 高效的读取能力，用于支撑快速查询

2. 特点

Parquet三个核心特征：

• 列式存储
• 自带Schema
• 具备Predicate Filter特性

3. 文件结构

一个Parquet文件的内容由Header、Data Block和Footer三部分组成。在文件的首尾各有一个内容为PAR1的Magic Number，用于标识这个文件为Parquet文件。Header部分就是开头的Magic Number。

Data Block是具体存放数据的区域，由多个Row Group组成，每个Row Group包含了一批数据。比如，假设一个文件有1000行数据，按照相应大小切分成了两个Row Group，每个拥有500行数据。每个Row Group中，数据按列汇集存放，每列的所有数据组合成一个Column Chunk。因此一个Row Group由多个Column Chunk组成，Column Chunk的个数等于列数。每个Column Chunk中，数据按照Page为最小单元来存储，根据内容分为Data Page和Dictionary Page。这样逐层设计的目的在于：

• 多个Row Group可以实现数据的并行加
• 不同Column Chunk用来实现列存储
• 进一步分割成Page，可以实现更细粒度的数据访问

Footer部分由File Metadata、Footer Length和Magic Number三部分组成。Footer Length是一个4字节的数据，用于标识Footer部分的大小，帮助找到Footer的起始指针位置。Magic Number同样是PAR1。File Metada包含了非常重要的信息，包括Schema和每个Row Group的Metadata。每个Row Group的Metadata又由各个Column的Metadata组成，每个Column Metadata包含了其Encoding、Offset、Statistic信息等等。

4. 查询举例

以下面的查询为例：

SELECT name, school FROM student WHERE age >= 22

Predicate Pushdown Filter的方式，在读取Parquet文件时，会先根据Footer Length找到Footer起始位置，读取Parquet中的Metadata，通过Metadata中的信息可以帮助我们进行相应的条件过滤。目前有两种实现，分别针对不同的数据类型。

(1) 整型数据

Column Metada中，有该Column Chunk中数据的Range信息: Max和Min。将过滤条件与Range信息进行对比，就可以知道是否需要加载该文件的数据。

File 0
	Row Group 0, Column Statistics -> (Min -> 20, Max -> 30)
	Row Group 1, Column Statistics -> (Min -> 10, Max -> 20)
File 1
	Row Group 0, Column Statistics -> (Min -> 6, Max -> 21)
	Row Group 1, Column Statistics -> (Min -> 25, Max -> 45)
	
通过对比过滤条件age >= 22，只需要加载File 0的Row Group 0和File 1的Row Group 1中的数据。

(2) 字符数据

先说说什么是字典编码。假设有个字段name，在10条数据中的值分别为：

name:
	bruce, cake, bruce, kevin, bruce, kevin, cake, leo, cake, bruce

我们可以对其编码，将其变为：

name:
	0, 1, 0, 2, 0, 2, 1, 3, 1, 0
dictionary:
	0 -> bruce, 1 -> cake, 2 -> kevin, 3 -> leo

这种方式在很多开源软件中都有使用，比如Elasticsearch，有两个优点：

• 可以节省存储空间
• 可以根据dictionary中的内容，过滤掉不符合条件的数据

在Parquet中，我们可以根据字符编码的特性来做相应的过滤。通过Column Metada中的信息，读取相应的Dictionary Page进行对比，从而过滤掉不符合条件的数据。

查询语句： SELECT name, school FROM student WHERE name = "leo"

File 0
	Row Group 0, Column 0 -> 0: bruce, 1:cake
	Row Group 1, Column 0 -> 0: bruce, 2:kevin
File 1
	Row Group 0, Column 0 -> 0: bruce, 1:cake, 2: kevin
	Row Group 1, Column 0 -> 0: bruce, 1:cake, 3: leo
	
通过对比过滤条件name = "leo"，只需要加载File 1的Row Group 1中的数据。

注：字符型的元信息类似于枚举型，主要看有没有。

四 总结

1.传统行式数据库的特性如下：

• 数据是按行存储的。
• 没有索引的查询使用大量I/O。比如一般的数据库表都会建立索引，通过索引加快查询效率。
• 建立索引和物化视图需要花费大量的时间和资源。
• 面对查询需求，数据库必须被大量膨胀才能满足需求。

2.列式数据库的特性如下：

• 数据按列存储，即每一列单独存放。
• 数据即索引。
• 只访问查询涉及的列，可以大量降低系统I/O。
• 每一列由一个线程来处理，即查询的并发处理性能高。
• 数据类型一致，数据特征相似，可以高效压缩。比如有增量压缩、前缀压缩算法都是基于列存储的类型定制的，所以可以大幅度提高压缩比，有利于存储和网络输出数据带宽的消耗。

3.参考文章：

• https://www.pianshen.com/article/6098918205/
• https://zhuanlan.zhihu.com/p/113917726
• https://zhuanlan.zhihu.com/p/111822325