数据库
1. 概况
1.1发展历史
1950年以前 没有文件概念，数据不具有独立性，没有数据管理方面的软件，外部存储器只有磁带、卡片和纸带，没有磁盘等直接存取设备；
50年代后期到60年代早期 计算机从科学计算拓展到信息管理，数据量快速增加；
1964年，世界上第一个数据库系统IDS（Integrated Data Storage）；
1968年，世界上第一个层次数据库IMS（Information Management System）诞生于IBM；
1970年，IBM的研究员Edgar F.Codd提出关系数据模型；
1974年，IBM推出关系模型的原型系统System R，同年IBM的Ray Boyce和Don Chamberlin提出SQL；
1976年，Peter Chen提出实体关系模型(Entity-Relationship Model，E-R Model；
1979年，第一个商业数据库Oracle Release 1诞生；
1989年，Postgres发布第一个版本，采用BSD版权；
1992年，SQL92国际标准草案形成；
1995年，Andrew Yu 和 Jolly Chen将Postgres增加SQL支持并开源到互联网上；
1996，MySQL发布，开源数据库开始发展；
2000年代，非关系型数据库NoSQL开始盛行，主要包括4种类型：文档数据库、列簇式数据库、键值数据库、图数据库；
2003-2006年，Google发表了奠定了业界大规模分布式存储系统的理论基础的三篇论文：Google File System、Google MapReduce、Google BigTable；
2010年，图数据库Neo4j发布；
2011年，结合SQL和NoSQL的NewSQL概念出现；
2012年，全球第一个Global Database, Google Spanner诞生；
2016年，Amazon发表了代表性的云数据库Aurora；
2018年，Oracle发表自治数据库(Oracle Autonomous Database)；
2019年，Google推出自学习数据库SageDB；
2019-2022年，clickhouse，doris等大数据实时数据库发布。
1.2发展阶段
第一阶段：人工管理阶段
20世纪50年代中期以前，计算机主要用于科学计算，外部存储器只有磁带、卡片和纸带等，还没有磁盘等存储设备，同时，软件系统也只有汇编语言，还没有数据管理方面的软件，数据处理方式主要是批处理。此时的数据不易保存，没有文件的概念。数据不具有独立性。
第二阶段：文件系统阶段
20世纪50后代后期到60年代中期，计算机开始不仅仅用于科学计算，还用于信息管理方面。随着数据量的增加，数据的存储、检索和维护问题成为了紧迫的需要，数据结构和数据管理技术迅速发展起来。此时数据已经可以长期保存，由文件系统管理数据，文件的形式已经多样化，数据具有一定的独立性。
第三阶段：数据库管理系统阶段
20世纪60年代后期，数据管理技术进入数据库系统阶段。数据库系统克服了文件系统的缺陷，提供了对数据更高级、更有效的管理。这个阶段的程序和数据的联系通过数据库管理系统（DBMS）来实现。
第四阶段：大数据阶段
进入21世纪之后，随着数据量的爆发式增长，各类大数据处理技术也应运而生，从中催生了NoSQL和 NewSQL相关技术。
2. 存储系统
2.1 存储结构
2.1.1 文件组织
Organization of Records in Files（文件中记录的组织）
组织
块：每个文件分成定长的存储单元，称为块（block）。块是存储分配和数据传输的基本单元。大多数数据库默认4~8KB块大小。一个块含多条记录。
定长记录
文件头：在文件的开始处，分配一定数量的字节作为文件头（file header），包含有关文件的各种信息。
空闲列表
在文件头中存储被删除的第一个记录的地址，用这第一个记录来存储第二个可用记录的地址，依次类推。被删除的记录形成一条链表，称为空闲列表（free list）
插入：使用文件头所指向的记录，并改变文件头的指针以指向下一个可用记录。
如果没有可用空间，新记录添加到文件末尾。
变长记录
方式：采用以下方式：
多种记录类型在一个文件中存储
允许一个或多个字段是变长记录类型（varchar）
允许可重复字段的记录类型（数组、多重集合）
一条记录的结构
一条有变长度属性的记录中属性连续存储，通常具有两部分：初始部分是定长属性，接着是变长属性
变长属性在记录的初始部分表示为一个对（偏移量，长度），其中：
偏移量表示在记录中该属性的数据开始位置
长度表示变长属性的字节长度
null值表示：使用空位图
例：如果salary是空值，则该位图的第4个位置置1，存储在12-19字节的salary值被忽略
分槽的页结构
结构：
记录条目的个数
块中空闲的末尾处
每个记录的位置和大小
特点：
实际记录从块的尾部开始连续排列，块中的空闲空间是连续的
指针指向块头记有记录实际位置的条目，而不是直接指向记录
插入：在空闲空间的尾部给插入的记录分配空间，并且将包含此记录大小和位置的条目添加到块头中
删除：分两步：
它所占用的空间被释放，并且它的条目被设置成被删除状态
块中被删除记录之前的记录被移动，使得由删除产生的空闲空间被重用，并且所有空闲空间存在于块头数组的最后一个条目和第一个记录之间
2.1.2 顺序文件组织（Sequential File Organization）
顺序文件组织（Sequential File Organization）
目的：为了高效处理按某个搜索码的顺序的记录而设计的
搜索码：一个属性或者属性的集合，不一定是主码、超码
指针链管理： 通过指针把记录链接起来，指向搜索码下一条记录
删除：直接用指针跳过连接，并将删除部分加入空闲列表
插入：如果有空闲空间，则直接插入；如果没有，则将记录插入到溢出块中；两操作都通过指针实现
注意：需要不时地重新组织文件以恢复顺序；文件重组时，重组代价高
2.1.3 多表聚簇文件组织（Multitable Clustering File Organization）
多表聚簇文件组织（Multitable Clustering File Organization）
目的：为高效执行连接操作设计
缺点：处理其他类型查询变慢
组织：用指针把这个关系的所有记录链接起来
2.2 文件类型
2.2.1 数据文件
1主要数据文件主要数据文件是数据库的起点，指向数据库中文件的其它部分。每个数据库都有一个主要数据文件。
2.2.2 辅助数据文件
2叔叔文件次要数据文件包含除主要数据文件外的所有数据文件。辅助数据文件辅助数据文件简称辅（助）文件，用于存储未包括在主文件内的其他数据。
2.2.3 日志文件
日志文件日志文件包含恢复数据库所需的所有日志信息。每个数据库必须至少有一个日志文件，但可以不止一个。
2.3 存储方式
目前大数据存储主要有两种方案可供选择：行存储（Row-Based）和列存储（Column-Based）。业界对两种方案有许多争持，争论的焦点是：谁能够更有效地处理海量数据，且兼顾安全、可靠、完整性。从目前发展情况看，关系数据库已经不适应这种巨大的存储量和计算要求，基本是淘汰出局。在已知的几种大数据处理软件中，Hadoop的HBase采用列存储，MongoDB是文档型的行存储，Lexst是二进制型的行存储。
- 概念介绍
行式存储（Row-basedstorage）常用于传统的关系型数据库。列式存储（column-based）是相对于行式存储说的。
行式存储：按行顺序存储表
列式存储：按列顺序存储表
两种存储的数据都是从上至下，从左向右的排列。行是列的组合，行存储以一行记录为单位，列存储以列数据集合单位，或称列族（column family）。行存储的读写过程是一致的，都是从第一列开始，到最后一列结束。列存储的读取是列数据集中的一段或者全部数据，写入时，一行记录被拆分为多列，每一列数据追加到对应列的末尾处。
- 对比分析
行存储和列存储的差异主要在数据写入和数据读取上，差别如下：
写入逻辑
（cud增改删）
读取逻辑
（r 检索查询）
2.3.1 行存储
写入是一次完成的，因此写入结果只有成功、失败两种结果
数据修改时，在指定位置写入一次。
将一列数据完全读出，如果需要其中几列的数据，就会存在冗余列，出去缩短处理时间的考量，消除冗余列的过程通常是在内存中进行的。
写入时可以保证数据的完整性；
写入时的性能比列存储高，消耗时间更少。
数据读取过程中会产生冗余数据；
数据解析比较复杂，因为每一行记录中保存了多种类型的数据，数据解析需要在多种数据类型之间频繁转换，很消耗CPU。
对写入性能、写入完整性要求比较高，但是对查询性能要求不高的场景。
主要是OLTP 操作型数据库。
2.3.2 列存储
需要把一行记录拆分成单列保存，写入次数明显比行存储多。
数据修改时，将磁盘定位到多个列上分别写入。
每次读取的数据是集合的一段或者全部，不存在冗余问题。
数据读取过程不会产生冗余数据；
数据解析会比较容易，每一列数据类型是同质的，不存在二义性问题，比如某列数据是整型（int），那么它的数据集合一定是整型；
列存储的数据，压缩时有很大的优势，主要是同一个数据列的数据重复度比较高。
写入时不能完全保证数据的完整性；
写入时的性能比列存储低。
对写入性能、写入完整性要求不高，但是对查询性能要求很高的场景。
主要是OLAP 分析型数据库。
如何改进
行存储和列存储都有其各自的缺点，假如我们希望能够使用某一种方式，但是又涉及到一些他们劣势方面的场景应用，那么该如何优化。
优化思路：行存储读取过程中避免产生冗余数据，列存储提高写入效率和数据完整性。
行存储的改进：减少冗余数据
1、首先是用户在定义数据时避免冗余列的产生；
2、其次是优化数据存储记录结构，保证从磁盘读出的数据进入内存后，能够被快速分解，消除冗余列。
列存储的改进：提高写入效率和数据完整性
1、在计算机上安装多块硬盘，以多线程并行的方式读写它们。多块硬盘并行工作可以减少磁盘读写竞用，这种方式对提高处理效率优势十分明显。缺点是需要更多的硬盘，这会增加投入成本，在大规模数据处理应用中是不小的数目。
2、考虑在写入过程中加入类似关系数据库的“回滚”机制，当某一列发生写入失败时，此前写入的数据全部失效，同时加入散列码校验，进一步保证数据完整性。
这两种存储方案还有一个共同改进的地方：频繁的小量的数据写入对磁盘影响很大，更好的解决办法是将数据在内存中暂时保存并整理，达到一定数量后，一次性写入磁盘，这样消耗时间更少一些。目前机械磁盘的写入速度在 20M-50M/ 秒之间，能够以批量的方式写入磁盘，效果也是不错的。
2.4 存储引擎
RAM与DAM
RAM（Random Access Machine model）假设计算机有无穷大小的内存，并且访问内存任何地址都用相同的单位时间。当机器实际内存满足某个算法理论需要的内存时，RAM可以很好的描述该算法的复杂度。然而假设机器实际内存不够时，操作系统将部分内存换出到磁盘并在需要时重新换回内存，虽然这对程序自身来说可以无感知，不过客观来看，还是不得不面对此刻的两种“内存”（内存+磁盘），他们的访问时间是100ns和10ms的区别，如此大的差距如果继续使用RAM一视同仁，那么此时对复杂度的分析是不准确的。
DAM（Disk-Access model也叫Standard External-Memory model)有如下定义：
- 一台机器有一个处理器、一个可以包含M个objects的内存以及无穷大小的外存
- 在一次I/O操作中，计算机可以在内存和外存之间传输包含B objects的block，其中1 < B < M
- 一个算法的Running Time可以定义为在算法执行期间I/O的次数、只用内存数据进行的计算可以认为是没有代价的
- 一个数据结构的大小可以定义成可以包含它的blocks数的大小
对于外存结构来说，无疑使用DAM来分析不同数据结构的优劣更为合适，只需要分析每种数据结构在各种操作中所涉及的I/O次数即可
读放大、写放大
写放大：Write amplification is the amount of data written to storage compared to the amount of data that the application wrote，也就是说实际写入磁盘的数据大小和程序要求写入数据大小之比
读放大：Read amplification is the number of I/O’s required to satisfy a particular query，也就是一次查询所需要的I/O数
2.4.1 哈希存储引擎
哈希存储引擎是哈希表的持久化实现，一般用于键值类型的存储系统。而大多传统关系型数据库使用索引来辅助查找数据，用以加速对数据库数据的访问。
2.4.2 树算法
在存储系统的设计中，存储引擎属于底层数据结构，直接决定了存储系统所能够提供的性能和功能。常见存储算法结构涵盖：哈希存储，B 、B+、B*树存储，LSM树存储引擎，R树，倒排索引，矩阵存储，对象与块，图结构存储等等。考虑到经常需要范围查找，因此其索引一般使用树型结构。譬如MySQL、SQL Server、Oracle中，数据存储与索引的基本结构是B-树和B+树。
2.4.3 Fractal tree算法
Fractal tree是B树一个变种。每个子节点对应的子树保存某个key值区间的数据。对于leaf节点，bp域指向leaf节点的有序数据结构。Leaf节点可以由多个有序的子结构组成，每个子结构构称作basement节点，实际上是一个弱平衡树形结构（或者数组）。
2.4.4 LSM树算法
主流的NoSQL数据库则使用日志结构合并树(Log-structured Merge Tree)来组织数据。LSM 树存储引擎和B树一样，支持增、删、改、随机读取以及顺序扫描。通过批量转储技术规避磁盘随机写入问题，极大地改善了磁盘的IO性能,被广泛应用于后台存储系统，如Google Big table、Level DB，Facebook Cassandra系统，开源的HBase，Rocks dB等等。
LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象，事实上，LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构，目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。
LSM树的核心特点是利用顺序写来提高写性能，但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得LSM树成为非常流行的存储结构。
3. 小结
本文介绍数据系统发展历史，文件系统，存储引擎。从服务器读写方式来讲，服务器cpu与IO的相关操作决定了内存读写，IO读写，顺序读写，随机读写；从存储引擎的方式来讲，又区分了行存储，列存储；逻辑上又分为，随机的哈希散列存储，折中的树存储结构，以及演变的分形树结构，分级存储的LSM树存储结构。
4. 文献参考
文件存储
https://blog.csdn.net/Ryansior/article/details/125549742
存储方式
https://blog.csdn.net/weixin_42009408/article/details/125360678
Innodb存储引擎
https://blog.csdn.net/solihawk/article/details/120104404
文件类型
https://www.idongde.com/q/7ab0ce056Eda9e4B/a1624645.shtml
存储引擎
https://blog.csdn.net/weixin_50205273/article/details/108623412
Mysql存储引擎
https://blog.csdn.net/lf1949/article/details/123552334