一、前言
数据在数据库中的存储方式就是数据存储结构。传统数据库由上到下，可以分为网络接入层、计算引擎层、存储引擎层、系统文件层，数据存储结构就是在存储引擎层，数据库通过存储引擎实现CRUD操作。不同的存储引擎决定了数据库的性能和功能，所以存储引擎层是数据库的核心。另外，在数据库中数据是以表的形式存储，所以存储引擎也可以称为表类型。
程序员必备的数据库知识（NineData）本文将介绍，HEAP、B+TREE、COLUMN-STORE、LSM-TREE、HASH等存储结构，这些不同的数据存储结构，导致不同数据库的索引、锁、事务等功能特性不同。下图是MySQL架构图，其中存储引擎有InnoDB、MyISAM、NDBCluster、Memory等。
高性能MySQL架构
二、逻辑结构
在介绍数据存储结构前，需要先了解数据库逻辑存储架构，常见关系型数据库逻辑架构单元从小到大是：块(block，MySQL称为page页)区(extent)段(segment)表空间(tablespace)。
块是数据库存储的最小单元，也是最小逻辑存储结构。不同数据库块的默认大小不一样，MySQL是16k，Oracle是8k。当数据写入块中，如果一条数据过大，就会连续占用几个块。块和块之间并不一定在物理上相连，只是在逻辑上使用双向链表关联，它们之间的物理位置有可能很远，所以数据库一般不以块作为最小的存储分配单位。
区（extent）是由一个或多个连续的块组成，区是Oracle和MySQL数据库的最小分配单位。段（segment）是由一个或多个区组成。它可以是连续的，也可以不连续。它是一个独立的逻辑结构，是存储对象、表、索引的数据对象，一个段属于一个数据对象，每创建一个新的的数据对象，就会创建新的独立段。不同类型的数据对象有不同的段：数据段、索引段、回滚段、临时段。
表空间（tablespace）是逻辑结构最高一级，数据库由一个或多个表空间组成，一个表空间则对应着一个或多个物理的数据文件，常用的表空间有数据表空间、索引表空间、系统表空间、日志表空间。下图是MySQLInnoDB逻辑存储架构图。
《MySQL技术内幕InnoDB存储引擎》
说明：如果表只存储了一条数据，那数据库也是要扫描整个最小存储单元（Oracle是block、MySQL是page）。这样设计是为了提高效率，因为物理I/O成本很大，不可能读、写一行数据就只扫描那行数据的磁盘。
三、HEAP
Heap表，也就是堆表，是Oracle数据库最常见、也是默认的表类型。堆表的数据会以堆的方式管理，意味着它的数据存取是随机的。数据库写数据时，会找到能放下此数据的合适空间。从表中删除数据时，则允许以后的写入和更新重用这部分空间。
比如先插入一个小行，接着插入一个大行，而且这个大行无法和小行无法存储在同一个块上，接着又插入一个小行。查询这三行数据它的默认排序是：小行、小行、大行。这些行并不按插入的顺序显示的，Oracle会找到能放下此数据的合适空间，而不是按照时间或者事务的某种顺序来存放。
堆表的特点是数据存储在表中，索引存储在索引里，这两者分开的。数据在堆中是无序的，索引让键值有序，但数据还是无序的。堆表中主键索引和普通索引一样的，都是存放指向堆表中数据的指针。
四、B+TREE
MySQLInnoDB引擎将数据划分为若干页（page），以页作为磁盘与内存交互的基本单位，页默认的大小为16KB。这样每次磁盘IO至少读取一页数据到内存中或者将内存中一页数据写入磁盘，通过这种方式减少内存与磁盘的交互次数，从而提升性能。page的格式如下图：
《MySQL技术内幕InnoDB存储引擎》
MySQLInnoDB引擎是使用B+Tree，B+Tree的特性是主键索引（又称聚集索引）的叶子节点保存的是真正的数据，而辅助索引（又称二级索引、非聚集索引）叶子节点的数据保存的是通过指向主键索引然后获得数据（也就是只根据辅助索引查询，需要进行一次回表）。
五、CLOUMN-STORE
传统的在线业务系统（OLTP）一般是以行存的方式，因为一行一行的写入读取符合在线业务场景。在联机分析处理系统（OLAP）中，常常需要统计分析某些列的数据，并对其进行分组、聚合运算，此时使用列存将会更高效。因为这样可以避免读取到不需要的列数据，另外同一列中的数据类型存储在一起也十分适合压缩，从而一个块可以存储更多的数据。
ApacheParquet是面向分析型业务的列式存储格式，一个Parquet文件的内容有Header、DataBlock和Footer三部分组成。其中DataBlock是具体存放数据的区域，它由多个RowGroup（行组）组成，每个RowGroup包含了一批数据。在RowGroup中，数据按列汇集存放，每列的所有数据组合成一个ColumnChunk（列块），一个列块具有相同的数据类型，不同的列块可以使用不同的压缩。因此一个RowGroup由多个ColumnChunk组成，ColumnChunk的个数等于列数。每个ColumnChunk中，数据按照Page为最小单元来存储，根据内容分为DataPage和IndexPage。如下图。
Parquet文件内容
六、LSM-TREE
Google的三驾马车之一BigTable，这篇论文提到LSM（Log-Structured-Merge-Tree日志结构合并树）数据结构。这之后LSM被多个数据库作为存储结构，比如HBase、TIDB、Oceabase，以及MySQL的MyRocks存储引擎。简单说LSM是一种磁盘严格顺序写入、数据分level存储、每level的数据都按主键（Key）排序后存储、各level中的数据会定期merge然后写入下一level等特性的数据结构。
我们知道顺序写的性能比随机写性能好很多，通过顺序写替代随机写，提升数据库性能是常见的方法之一，比如WAL技术。LSM的数据数据写入是日志式的（appendonly）顺序写入，写入数据时直接追加一条新记录。
当进行写数据时。先写入Memtable和预写日志(WriteAheadLogging,WAL)。因为Memtable是内存操作，防止掉电需要将记录写入磁盘中的WAL保证数据不会丢失。当MemTable写满后会被转换为不可修改的ImmutableMemTable，并创建一个新的空MemTable。后台线程会将ImmutableMemTable写入到磁盘中形成一个新的SSTable文件，并随后销毁ImmutableMemTable。
SSTable(SortedStringTable)是LSM树中在持久化存储的数据结构，它是一个有序的键值对文件。LSM不会修改已存在的SSTable，LSM在修改数据时会直接在MemTable中写入新版本的数据，并等待MemTable落盘形成新的SSTable。这样保证在同一个SSTable中key不会重复，但是不同的SSTable中还是会存在相同的Key。
当读取数据时。因为最新的数据总是先写入MemTable，所以在读取数据时首先要读取MemTable然后从新到旧搜索SSTable，找到某个key第一个版本就是其最新版本。我们知道，刚写入的数据是很有可能被马上读取的，因此MemTable还起到了很好的缓存作用。如下图。
Log-Structured-Merge-Tree日志结构合并树
随着不断的写入SSTable数量会越来越多，数据库持有的文件句柄(FD)会越来越多，读取数据时需要搜索的SSTable也会越来越多。另一方面对于某个Key而言只有最新版本的数据是有效的，其它记录都是在白白浪费磁盘空间。因此对SSTable进行合并和压缩(Compact)就十分重要。在合并和压缩的过程中，会遇到读放大、写放大、空间放大等问题，这些不同的问题需要做取舍，也就诞生了多种合并压缩策略。
七、HASH
RedisHASH是字符串字段和值之间关系的映射表，适合用于存储对象。比如：一个用户有多个属性字段，如：姓名、年龄、性别等等。
RedisHASH
如上图，左边是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