一、前言

数据在数据库中的存储形式就是数据存储构造。传统数据库由上到下，能够分为网络接入层、计算引擎层、存储引擎层、系统文件层，数据存储构造就是在存储引擎层，数据库通过存储引擎实现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