一、前言
数据在数据库中的存储形式就是数据存储构造。传统数据库由上到下，能够分为网络接入层、计算引擎层、存储引擎层、系统文件层，数据存储构造就是在存储引擎层，数据库通过存储引擎实现 CRUD 操作。不同的存储引擎决定了数据库的性能和性能，所以存储引擎层是数据库的外围。另外，在数据库中数据是以表的模式存储，所以存储引擎也能够称为表类型。
本文将介绍，HEAP、B+TREE、COLUMN-STORE、LSM-TREE、HASH 等存储构造，这些不同的数据存储构造，导致不同数据库的索引、锁、事务等性能个性不同。下图是 MySQL 架构图，其中存储引擎有 InnoDB、MyISAM、NDB Cluster、Memory 等。
二、逻辑构造
在介绍数据存储构造前，须要先理解数据库逻辑存储架构，常见关系型数据库逻辑架构单元从小到大是：块(block，MySQL 称为 page 页) > 区(extent) > 段(segment) > 表空间(tablespace)。
块是数据库存储的最小单元，也是最小逻辑存储构造。不同数据库块的默认大小不一样，MySQL 是 16k，Oracle 是 8k。当数据写入块中，如果一条数据过大，就会间断占用几个块。块和块之间并不一定在物理上相连，只是在逻辑上应用双向链表关联，它们之间的物理地位有可能很远，所以数据库个别不以块作为最小的存储调配单位。
区（extent）是由一个或多个间断的块组成，区是 Oracle 和 MySQL 数据库的最小调配单位。段（segment）是由一个或多个区组成。它能够是间断的，也能够不间断。它是一个独立的逻辑构造，是存储对象、表、索引的数据对象，一个段属于一个数据对象，每创立一个新的的数据对象，就会创立新的独立段。不同类型的数据对象有不同的段：数据段、索引段、回滚段、长期段。
表空间（tablespace）是逻辑构造最高一级，数据库由一个或多个表空间组成，一个表空间则对应着一个或多个物理的数据文件，罕用的表空间有数据表空间、索引表空间、零碎表空间、日志表空间。下图是 MySQL InnoDB 逻辑存储架构图。
《MySQL 技术底细 InnoDB 存储引擎》阐明：如果表只存储了一条数据，那数据库也是要扫描整个最小存储单元（Oracle 是 block、MySQL 是 page）。这样设计是为了提高效率，因为物理 I / O 老本很大，不可能读、写一行数据就只扫描那行数据的磁盘。
三、HEAP
Heap 表，也就是堆表，是 Oracle 数据库最常见、也是默认的表类型。堆表的数据会以堆的形式治理，意味着它的数据存取是随机的。数据库写数据时，会找到能放下此数据的适合空间。从表中删除数据时，则容许当前的写入和更新重用这部分空间。
比方先插入一个小行，接着插入一个大行，而且这个大行无奈和小行无奈存储在同一个块上，接着又插入一个小行。查问这三行数据它的默认排序是：小行、小行、大行。这些行并不按插入的程序显示的，Oracle 会找到能放下此数据的适合空间，而不是依照工夫或者事务的某种程序来寄存。
堆表的特点是数据存储在表中，索引存储在索引里，这两者离开的。数据在堆中是无序的，索引让键值有序，但数据还是无序的。堆表中主键索引和一般索引一样的，都是寄存指向堆表中数据的指针。
四、B+TREE
MySQL InnoDB 引擎将数据划分为若干页（page），以页作为磁盘与内存交互的根本单位，页默认的大小为 16KB。这样每次磁盘 IO 至多读取一页数据到内存中或者将内存中一页数据写入磁盘，通过这种形式缩小内存与磁盘的交互次数，从而晋升性能。page 的格局如下图：
MySQL InnoDB 引擎是应用 B +Tree，B+Tree 的个性是主键索引（又称汇集索引）的叶子节点保留的是真正的数据，而辅助索引（又称二级索引、非汇集索引）叶子节点的数据保留的是通过指向主键索引而后取得数据（也就是只依据辅助索引查问，须要进行一次回表）。
五、CLOUMN-STORE
传统的在线业务零碎（OLTP）个别是以行存的形式，因为一行一行的写入读取合乎在线业务场景。在联机剖析解决零碎（OLAP）中，经常须要统计分析某些列的数据，并对其进行分组、聚合运算，此时应用列存将会更高效。因为这样能够防止读取到不须要的列数据，另外同一列中的数据类型存储在一起也非常适宜压缩，从而一个块能够存储更多的数据。
Apache Parquet 是面向剖析型业务的列式存储格局，一个 Parquet 文件的内容有 Header、Data Block 和 Footer 三局部组成。其中 Data Block 是具体存放数据的区域，它由多个 Row Group（行组）组成，每个 Row Group 蕴含了一批数据。在 Row Group 中，数据按列会集寄存，每列的所有数据组合成一个 Column Chunk（列块），一个列块具备雷同的数据类型，不同的列块能够应用不同的压缩。因而一个 Row Group 由多个 Column Chunk 组成，Column Chunk 的个数等于列数。每个 Column Chunk 中，数据依照 Page 为最小单元来存储，依据内容分为 Data Page 和 Index Page。如下图。
六、LSM-TREE
Google 的三驾马车之一 BigTable，这篇论文提到 LSM（Log-Structured-Merge-Tree 日志构造合并树）数据结构。这之后 LSM 被多个数据库作为存储构造，比方 HBase、TIDB、Oceabase，以及 MySQL 的 MyRocks 存储引擎。简略说 LSM 是一种磁盘严格程序写入、数据分 level 存储、每 level 的数据都按主键（Key）排序后存储、各 level 中的数据会定期 merge 而后写入下一 level 等个性的数据结构。
咱们晓得程序写的性能比随机写性能好很多，通过程序写代替随机写，晋升数据库性能是常见的办法之一，比方 WAL 技术。LSM 的数据数据写入是日志式的（append only）程序写入，写入数据时间接追加一条新记录。
当进行写数据时。先写入 Memtable 和预写日志(Write Ahead Logging, WAL)。因为 Memtable 是内存操作，避免掉电须要将记录写入磁盘中的 WAL 保证数据不会失落。当 MemTable 写满后会被转换为不可批改的 Immutable MemTable，并创立一个新的空 MemTable。后盾线程会将 Immutable MemTable 写入到磁盘中造成一个新的 SSTable 文件，并随后销毁 Immutable MemTable。
SSTable (Sorted String Table) 是 LSM 树中在长久化存储的数据结构，它是一个有序的键值对文件。LSM 不会批改已存在的 SSTable，LSM 在批改数据时会间接在 MemTable 中写入新版本的数据，并期待 MemTable 落盘造成新的 SSTable。这样保障在同一个 SSTable 中 key 不会反复，然而不同的 SSTable 中还是会存在雷同的 Key。
当读取数据时。因为最新的数据总是先写入 MemTable，所以在读取数据时首先要读取 MemTable 而后从新到旧搜寻 SSTable，找到某个 key 第一个版本就是其最新版本。咱们晓得，刚写入的数据是很有可能被马上读取的，因而 MemTable 还起到了很好的缓存作用。如下图。
日志构造合并树随着一直的写入 SSTable 数量会越来越多，数据库持有的文件句柄 (FD) 会越来越多，读取数据时须要搜寻的 SSTable 也会越来越多。另一方面对于某个 Key 而言只有最新版本的数据是无效的，其它记录都是在白白浪费磁盘空间。因而对 SSTable 进行合并和压缩 (Compact) 就非常重要。在合并和压缩的过程中，会遇到读放大、写放大、空间放大等问题，这些不同的问题须要做取舍，也就诞生了多种合并压缩策略。
七、HASH
Redis HASH 是字符串字段和值之间关系的映射表，适宜用于存储对象。比方：一个用户有多个属性字段，如：姓名、年龄、性别等等。
如上图，右边是 Key 对应左边存储空间，左边的存储空间叫 HASH，也就是说 HASH 是数据类型，他不是具体的一个数据，而是存储空间上的一堆数据。它底层有 ziplist、hashtable 两种数据编码。
ziplist 表，又称为压缩列表，是一种非凡编码的双链表，用于存储字符串或整数，从而进步内存应用效率，这也是 HASH 数据类型默认应用的编码格局。但内存使用率高了，那么它的查问操作速度绝对升高，因为多了编码解码的操作。ziplist 是典型工夫换空间的设计（个别索引是用空间换工夫）。
hashtable 表，又称为哈希表，是 HASH 数据类型中，当数据过多或多长时由 ziplist 优化而来，底层数据结构与 ziplist 不同，且数据结构不可逆。具体应用哪种编码格局，Redis 会依据状况本人抉择更适合的编码格局，这对于用户齐全通明。
八、总结
通过上述五种数据存储构造的介绍，咱们能够整顿出以下表格：
数据库是用于存储数据的，为了不失落数据每次写须要做长久化，也就是数据每次写都要存储在磁盘上。磁盘绝对 CPU、内存、缓存等设施，它的 IO 处理速度慢了几个数量级，即便是 SSD，磁盘 IO 也是远低于内存的读写速率。所以数据库为了进步性能，就须要在磁盘 IO 上做出最佳抉择。这些不同的数据存储构造，就是面对不同的数据以及业务场景，来进步数据库性能。当然古代数据库还要对数据进行压缩、解压、散布等等运算操作，则须要应用 CPU 等资源，这些不再本文阐述范畴内。
本文介绍了五种常见数据存储构造，另外还有图、表格、链式、R-TREE 等数据结构并未波及，当然本文也只是对数据库存储构造的常识抛砖引玉，有趣味的同学能够对每一种数据存储构造做更具体和深刻的学习。
最初
司马辽太杰是 NineData 工程师。NineData 向企业和集体提供高效、平安的数据库 SQL 开发、数据库备份、数据复制 / 迁徙 / 集成、数据比照等性能，是一个 SaaS 服务开箱即用，能够疾速晋升企业 SQL 开发效率，保障企业数据安全。NineData 官网地址：https://www.ninedata.cloud