Btree存储结构

简介

Btree数据结构自1970年被提出之后，被广大的数据库使用者接受BTree目前不太可能被新技术淘汰，而日志索引结构的Lsm-Tree未来前景十分可观。

Btree特点

和SSTable仅仅只有一点类似：B-tree保留按键排序的 key/value对，这样可以实现高效的 key-value查找和区间查询，除此之外没有其他的相似点。

下面是Btree的特点：

• 和日志存储结构不同的是，Btree将数据分为固定的数据页，每一个数据页固定大小，通常为4KB，InnoDB一个数据页固定设置为16KB。
• 更新数据在原结构上进行更新，也就是使用新数据页覆盖旧的数据页，所以更新的代价相对于日志结构要大很多的。
• 数据页存在和磁盘对应的唯一标识，同时数据页之间通过链表指针串联，但是指针存储的不是内存上的地址，而是磁盘的地址，
• 新增数据如果数据页内容不足需要进行页分裂，同时父节点需要包含新分裂的页，而页分裂很容易造成磁盘碎片和数据的排序，同时因为内部需要维持数据排序开销不小。

为什么数据页要固定大小？ 这和磁盘的读写有关，传统机械硬盘为512b最小单位，而SSD通常为4KB最小单位读写，所以数据页设计为和磁盘兼容的形式存储有利于顺序读写，同时可以最大化利用磁盘空间。

Btree优化和可改进点

• 压缩存储：使用缩略的键信息，因为对于树中间一个数据行来说只要提供开始和结束的位置即可，这样可以在有限的数据页存储更多的数据。
• 数据页排序：虽然数据页可以存储在不同的磁盘空间，但是对于某些需要范围查询的情况下需要对于磁盘进行顺序查找，而此时数据页的随机查询就会出现问题
• BTree到B+树的优化，优化的方式也十分简单易懂，在各层都加链表加快索引查找，这种甚至不能叫优化只能说是改进。
• 使用写时复制替代覆盖页的方式，在修改页的时候不对原数据改动，将写入新的父页并且更新旧引用。

Btree和LSM-Tree对比

Btree的读写速度快于LSM-Tree，因为一次IO读写可以索引到大量的数据页，而LSM-Tree需要跨越多个压缩段才可能找到数据。但是LSM-Tree的读写速度要快于Btree，同时存储效率要比Btree要高，因为压缩和合并分段之后数据间隙之间基本不存在数据间隙碎片。

所以LSM-Tree适用于读写多的场景，而Btree因为需要高效查询设计上要复杂非常多所以为了服务查询性能可以容忍写入和删除的额外开销。

单纯对比数据结构可能比较枯燥，这里从老外的网站上找了一份Mysql和LevelDB的对比，这两款基本可以代言Btree和LSM-Tree这两种数据结构了。可以看到LevelDB要比Mysql的出现晚上不少，这和BigTable有着密切关系，也和网络时代的发展和互联网的用户量指数上升有关系。

OLTP和OLAP

特征

单从名字的区分，这两个类型分别针对事务和针对分析，由此引发了不同的完全不同的数据结构和存储形式，同时侧重点和服务范围不同，注意这两者并不能说谁优势谁劣势，因为OLAP说白了是在OLTP上演化而出现的。

如果看不清，可以看看甲骨文提供的一个表格：

OLTP：在线事务处理。用于处理数据量较小的事务为主的业务，要求的是高吞吐高响应，一般为web应用程序，主要面向广大用户群体，适用于解决生活中80%左右的业务和系统问题。

OLAP：在线分析处理。主要基于大数据量的数据搜索和汇总，随着时间变化而进行数据分析进行数据支撑。一般出现在中大型公司的较大型项目中。

数据仓库

事务型号数据库这里不再赘述了，相信大家也很熟悉，这里说说数据仓库是什么？

数据仓库是上世纪90年代被提出的放弃基于传统事务 OLTP结构的数据库分析，转为使用单个数据仓库进行数据分析的方式，简单理解就是讲数据和业务剥离，只保留数据部分进行存储，通常为了方便分析会使用[[《数据密集型系统设计》列式存储]]引擎和前面提到的[[《数据密集型型系统设计》SSTable和LSM-Tree]]数据结构。

优势

数据仓库有下面的优势。

• 面向主题：数据仓库可以高效分析关于特定主题或职能领域（例如销售）的数据。
• 集成：数据仓库可在不同来源的不同数据类型之间建立一致性。
• 相对稳定：进入数据仓库后，数据将保持稳定，不会发生改变。
• 反映历史变化：数据仓库分析着眼于反映历史变化。

存储形式

数据仓库一般不存在于小公司，因为根本没有那个资金支撑也没有，而是面对较大公司多达10几个系统数据规模的存在形式，所以对于很多人来说可能就是围观看造火箭，看懂了好像也没啥价值。

结构图

下面是整个数仓系统的结构

进化

数据仓库到了现在又出现了进一步的转变，大数据也被分为了很多个方向，这些都是战未来的东西，这里简单提炼一下概念：

• 数据挖掘
• 预测和统计
• 人工智能和机器学习

数据湖

注意数据库并不是指比数据仓库大很多倍的数据仓库或者数据库集群，他是完全不同的概念，数据仓库是已经被整理 数据湖主要用于存储大量迥然不同并且没有进行分类筛选的数据，数据湖对于分析人员来说是最为自由的一种，可以形象看作垃圾池掏金子，收益和代价并存，更多时候是把数据湖转为数据仓库。

应用

• 数据库 比较流行的有：MySQL, Oracle, SqlServer等。
• 数据仓库 比较流行的有：AWS Redshift, Greenplum, Hive等。

分析模式

对于数据仓库的分析模型，现今通常有两种方式：星型模型和雪花模型。

星型模型

星型模型也别叫做纬度模型，这个模型针对的是非强依赖的数据关系分析，比较典型的必入电商系统和购物网站，虽然商品，订单，库存，广告等等看似没有什么关系，然而这些数据就像是星星一样分散，有着千丝万缕的直接依赖或者间接依赖关系。 星型模型的数据更像是星星和月亮的关系，核心通常位于中间， 而四周散布关系模型。

雪花模型

雪花模型要比星型模型设计上规范很多，也是对于维度模型的进一步拆分，比如对于商品表引入更加细分的品牌和分类进行更进一步的细分，也类似超市的商品分类。

小结

这一节点从OLAP讲到数据仓库，再讲到两种主流的分析方式，星型模型和雪花模型。 当然这些内容都是简单介绍，读者可以根据自己感兴趣的点进行深入和熟悉。

列式存储

介绍

对于传统的业务数据库并且用户量较小的公司来说，通常使用关系型数据库，而关系型数据库基本以Btree数据结构作为核心，这些数据库基本都是行存储，行存储比较符合理解思维，然而实际上对于数据分析而言，行数据往往会造成长时间的时间等待，并且如果需要对于数据进行实施分析作为业务决策，使用行存储分析显然系统开销是无法接受的，由此引入了[[OLTP和OLAP]]。

之前提到的内容都是行式存储，有些情况下列存储更利于数据管理，特别是对于事务关系数据库行存储结构不利于单一列分析，比如我们想要存储某一分类的价格趋势，行存储需要扫描所有行求和，而列存储直接把一整列拿出来求和即可，两者效率自然不用多说。

列存储结构特点

• 所有列值紧凑存储在一起
• 通常比行存储更有利于理解
• 可用于非关系型数据库，当然也可以用于关系型数据库。（反过来行存储就不适用这条规则了）

列压缩

列式存储意味着讲同类数据压缩到不同的段，这对于存储结构来说是有利的，通常列压缩在数据仓库使用位图的形式存储。

因为列存储的都是同一个数据类型的数据，所以可以针对不同的数据类型进行优化存储，这样也意味着比行存储更少的空间压缩更多的数据，比如对于一些整型数据在压缩存储的时候可以使用位模式存储。也就是直接存数字的二进制位编码，列查询的时候进行位操作即可。

下面是一个典型的列存储和压缩的例子：

存储位图可能人不是很好理解和计算，但是计算器来说就不一样了，位元算操作远远高于数学运算。

另外除开列压缩以外，列的存储还以一个列族的概念，列族存在于Cassandra和HBase这两个数据库，而列族这个概念继承自BigTable。 但是我们之前介绍[[《数据密集型型系统设计》SSTable和LSM-Tree]]讲述基本还是行存储方式和实现。

列族：其实指的是把一行中的所有列和行主键保存到一起，并且不使用列压缩的形式存储。其实这种用行转列基本就可以实现，所以列族严格意义上依然是行存储的变体，和真正的列存储还是存在差异的。

列排序

相对于行存储，列的排序其实并没有多重要，因为他不关心数据归属而是数据的整理，和[[SSTable]]一样，列排序最好的方式也是通过追加压缩合并的方式，然后利用索引和一些天然的有序数据结构完成存储。

注意列排序一般不会针对单列进行排序，因为没有多少意义，至于原因这里依然强调单列没有办法知道数据的归属。

列排序的第一个优势是可以对列的重复值进行压缩，比如性别通常只有男和女，这时候重复的列存储是没有必要的。

列排序的另一个优点是多列排序可以快速的定位某一列的极值情况和方便快速的分组或者过滤查询。

C-Store最早引入了 一 种改进想蓓，井被商业数据仓库 Vertica。

最后，面相列存储通常会具备多个排序顺序，但是多列排序很难维护，所以更常见的情况是引入二级索引维护，和行存储的索引维护不同，行存储的二级索引通常指向数据行（或者向InnoDB一样指向主键，不过这种处理比较特殊），列存储二级索引通常指向值。

视图

列存储中一个十分重要的优化特性是引入试图对于临时查询进行加速，数据仓库中的SQL中经常会碰到聚合函数的查询通常会想到使用缓存进行存储。 列存储的缓存被叫做标准视图，注意这个视图并不是逻辑临时结构，而是真实物理视图，列存储相比行存储对于物理存储的数据有效和可用性高很多，OLTP系统不适用物理视图主要原因是缓存失效很快并且需要应对低延迟高响应的查询，而数据仓库由于主要做数据分析数据静态情况更多。 视图的特殊情况叫做数据立方体，数据立方体的概念类似于列存储的“行聚合”和“列聚合”交叉查询的方式：

从上面的图可以看到，数据分为多个维度进行分析和查询，通过多维度角度可以把多个分类模型的数据放到一起进行交叉统计，这对于数据分析人员来说无疑省去大量的准备工作，将这种数据立方物化之后的查询效率也十分高。

物化数据毫无疑问让数据查询更快，因为数据已经预先准备，但是数据立方的缺点和缓存的缺点一样是不能频繁改动，否则失去其本身意义。

总结

主要的内容集中在Key/value的数据库发展和哈希索引，以及后续的Btree和LSM-Tree上，可以看到BTree出现最早但是经历了30多年依然长盛不衰，一时半会应该还没有更优秀的数据结构替代，而LSM-Tree则比较符合未来和现代的发展潮流，因为他存储形式更自由，并且非常适合用于列式存储和列压缩以及数据分析，总之这篇笔记更多的是让读者了解更广阔的数据视野。

写在最后

这篇除开书本的内容之外，个人对于其他内容做了一些补充，如果有不同的看法欢迎讨论，如果文中有错误欢迎批评指正。