[toc]

数据库作业

存储技术

在数据库中，在数据存储方面，一般分为定长，和变长，两种方式。采用定长存储的时候，每条记录分配的长度是固定。不论记录的内容，是否使用完分配的地址，都采用固定的空间。采用变长存储，每条记录分配的地址长度不是固定，很多时候，分配的都是记录实际存储位置的，一个地址，在查找的过程中，根据地址找到实际的数据位置。
针对变长，和定长，的优缺点，我自己归纳如下：

定长：

优点：

1. 策略简单，程序实现方便，不需要过多的维护指针的地址内容。如果是相邻存储。所有地址，都有可能通过直接计算得出地址。（实际上，在实现作业三的时候，采用的就是定长地址）。
2. 方便批量顺序读取，大数量读取的时候，效率高。
3. 数据集中，不易产生碎片

缺点：

1. 空间浪费，如果当字段大部分记录长度短。其中有某一个记录的长度很大，按定长存储策略，就会造成空间很大的浪费：

   例如：我在实现作业三的过程中，曾经创建过这样一个shcema的数据表['int', 'text(6)', 'text(50)', 'int']。在第三个text字段，我采用分配50个字节记录。生成1w条数据的时候，大约占用内存700多kb（而不是680k，因为用了，分块存储，1K数据一块，为了对齐，中间有些空间，为空）。但是，采用['int', 'text(6)', 'text(500)', 'int']这样的schema，第三个text字段采用500个字节，同样是1w的数据量，大约占用内存19.1M。如下图：

   数据占用内存的截图

2. 对于极大的字段内存空间节约会更理想。例如有些数据库字段存放电影。有些记录，是2G的电影内容，有些是电影的标题，如果采用变长字段，将会极大的减少数据库的大小

变长：

优点：

1. 节省空间，特别是在记录，长度不一的时候，删除修改方便。(只需要修改，或标记该地址为空闲)

缺点：

1. 程序实现复杂，维护记录地址，需要小心
2. 对于跨块记录存储的记录，要小心。
3. 数据不集中，读取数据局部性不高，影响i/o效率

变长记录，在部分商业数据库中的应用

sqlite 应用变长记录

sqlite定位为嵌入式数据库，因此在数据库空间大小上，要求更严格，因此采用变长记录更为合理，更符合产品定位

在sqlite的官网文档中，提供，vacuum，命令，用于在删除大量记录之后，手动释放sqlite空闲空间使得数据库文件压缩到最小

由于sqlite采用的是变长存储。在大量插入数据的时候，数据库空间，会自发增长，当在原有数据库中大量删除数据时，就会有大量的存储空间，被标为空闲，如果后面再插入数据，优先在这些空闲块中插入数据。
这就存在一个问题，sqlite数据库，会只增加，不缩小。vacuum命令，就提供一种手动是否空闲空间的工具，使得空间压缩到最小。

插入大量数据sqlite大小

删除数据后sqlite大小

运行vacuum命令之后，数据大小

MongoDB MMAPV1引擎应用定长记录

这一部分，没有做实验，资料来源于阅读MogoDB官方文档

MogoDB，定位为 Nosql 数据库。属于文档型数据库，在OLAP，和OLTP上都有应用。其中MMAPV1 (Mobile Messaging Access Protocol) 存储引擎是原声引擎，官网文档，定义如下

`MMAPv1 is MongoDB’s original storage engine based on memory mapped files. It excels at workloads with high volume inserts, reads, and in-place updates.`

之所以，提供高新能的插入，读取，和原地修改，与MMAPV1引擎的数据存储策略有关。在MMAPV1引擎中，所有数据，相邻存储，初始空间分配大小为2倍(2 size of Allocation)分配空间的时候尽量是2的倍数空间大小。小于2M的数据，按数据量的2倍分配。大于2M数据，按2M的倍数分配。(如14.1M数据，会分配16M的空间)这样带来的好处是，充分利用空间，做到跟操作系统地址对齐，读取效率更高。同时，2 size of Allocation策略，也能使得数据在修改的时候，尽可能的保证, high volume inserts, reads, and in-place updates.
在mogoDB中，如果是采用MogoDB作为OLAP数据仓库，么么针对，一些不常修改的数据，可以采用full fit策略，这样能使得数据实际大小和占用空间大小，尽可能的接近，这种策略能最大程度上使用磁盘。

不论是定长存储，还是变长存储。都要针对特定的数据库产品，采用特定的策略

索引技术

在绝大部分数据管理系统中，都会应用到索引技术，来加快，数据查找的效率，其中索引，分类有稠密索引，和稀疏索引。种类，有，B树索引，哈希索引，R-树索引，kd-树索引等。在mysql中，默认的建立索引的方式为B树索引，所以我主要了解，只有B树索引：
实际的产品数据库中，数据量大的时候大多采用多级索引，即，在索引上，再建索引，上层索引一定是稀疏索引

索引技术在mysql中帮助提高查询效率

info_schema表，为mysql优化提供了很多有用的信息

show create table titles 查看表结构，和索引细节

这次实验，采用的是mysql中官方发布的employees数据库，employee表结构如下图

employee表结构

表数据量

命令行查看表索引信息，explain子句信息

通过输出信息，了解到表之后，一个3个字段的多列索引。输出的rows字段，为442308，表明在where条件上的select查询语句，用到的策略是全表扫描，

myssql 添加索引，及不添加索引，前后效率效果比对

如果在表上加上索引，rows预计需要扫描的行数量，就缩减为69行。能大大加快表的查询

用过索引，查询预计行数大大减小

创建数据库索引，注意事项

数据库索引，确实能在生产环境中给数据查询带来很大的效率提升。大部分时候带来的提升，可能会有几倍，或者几十倍的效率提升空间。但是并不是所有时候都适合创建索引

比如。如果数据库的量比较大，往往在新建索引的时候可能会花费几十分钟，甚至是几个小时，而在创建索引的过程中，数据库是阻塞的。这个时候所有的请求都会等待，这在实际的生产环境中，很可能是不被容许的。
除此之外，如果会在一张表上，创建多个索引的话，如果在一个sql语句中创建多个索引，会比每个sql语句创建一个sql语句效率来的更高。时间有时候能缩短为几分之一 。
在表中插入索引，的确能给数据库的查询带来很大的提升，但是同时在数据进行插入的时候，对索引的维护，也需要一些代价，因此在实际生产的环境中，平衡读取和写入数据的时间，合理利用索引技术也是必须要注意的技能

EXPLAIN语法各列字段的意义：

• key: 优化器，使用的索引
• rows: 估计结果行数
• possible_keys: 可能用到的索引，可以通过show indexes 来查看表格
• ref:用来比较的列，或者常量
• type:const表示只有一行结果。ref，表示具有匹配的索引，都会被用到
• select_type: simple表示简单查询 derived 表示查询的表，不是一个物理表，比如，在子查询中再查询。
• table: 用到的表格
• key_len: 索引，结构长度
• filtered:返回结果的行占需要读到的行

sql优化的工作流

1. 截取sql语句
2. 识别出分类有问题的sql语句
3. 确认sql语句的操作
4. 分析sql语句和辅助信息
5. 优化sql语句
6. 验证优化的结果

从mysql中截取sql语句的方法，有全面查询日志，慢查询日志，进程列表这几个方法全面查询日志，和慢查询日志，主要通过设置mysql数据库的设置选项，其中全面查询日志，可以在前期数据库不太大的情况下使用，但是在生产环境下使用会严重影响到数据库的性能。慢查询日志通过记录数据库中查询时间超过某个阀值的时候，记录下查询信息，其中日志信息包括很多数据，通过日志可以了解到，语句执行频率，来源用户以及主机。等个得到的执行时间，处理过的行，以及结果集的大小。的最小，最大，平均以及中间值的统计信息。同事也有一些开源的工具，能对日志文件进行分析。

当从日志文件中分析出需要优化的sql语句止呕胡，就可用通过上面EXPLAIN 语法查看具体sql的执行计划，和表格上现在所拥有的一些索引信息，已经字段长度等等，通过查看具体的EQP，创建合适的索引进行查询优化。

在优化了查询语句之后，需要在实际的数据中验证优化效果。最后应用到生产环境中去。

mysql 中的join算法

mysql 默认的采用的是简单嵌套查询，基于的实际假设是：数据库表大小，都能完全放入机器内存当中。
我设计了一个实验，让myslq，对一个129M 和1.7G的数据进行链接（不超过内存，机器内存16G大小），建立约束条件。查看myssql实际的io数量。实际的数据大小，和数据内容如下：两个数据集大小

两个数据的数据大小

数据集一字段内容

数据格式

数据集二字段内容

数据格式2

给两个数据集创建外键约束，在创建约束过程中，会使用连接算法

进行连接操作

用iostat这个工具，监控磁盘io数据输出。输出的结果如下下图所示：

磁盘io数据输出

工具输出的数据，是以累计值，数据，所以两者差额，约为7.2G，7.2G/1.5的数据，大约为5得出的io统计量为5倍io
从上面的结果来看，在建立外键约束，之后，查询的效率就高很多能在0.0072秒只能返回查询结果

NewSQL系统的一些技术

内存查找结构，skip-list

skiplist介绍

Skip List 是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要 O(log n) 平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表 (因此得名)。所有操作都以对数随机化的时间进行。Skip List 可以很好解决有序链表查找特定值的困难。

一个跳表，应该具有以下特征：

1. 一个跳表应该有几个层（level）组成；
2. 跳表的第一层包含所有的元素；
3. 每一层都是一个有序的链表；
4. 如果元素 x 出现在第 i 层，则所有比 i 小的层都包含 x；
5. 第 i 层的元素通过一个 down 指针指向下一层拥有相同值的元素；
6. 在每一层中，-1 和 1 两个元素都出现 (分别表示 INT_MIN 和 INT_MAX)；
7. Top 指针指向最高层的第一个元素。

就像这张表的结构

skip-list

Skip List 构造步骤：

1. 给定一个有序的链表。
2. 选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。
3. 为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top 指针指向该层首元素
4. 重复 2、3 步，直到不再能选择出除最大最小元素以外的元素

skip-list 和二叉树中的比较

如果单纯比较性能，跳跃表和二叉树可以说相差不大，但是加上并发的环境就不一样了，
如果要更新数据，跳跃表需要更新的部分就比较少，锁的东西也就比较少，所以不同线程争锁的代价就相对少了，
而二叉树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。性能也就不如前者了。
在并发环境下skiplist有另外一个优势，二叉树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，
而skiplist的操作显然更加局部性一些，锁需要盯住的节点更少，因此在这样的情况下性能好一些。

高并发，采用的 replica set技术

采用 quoram 机制+守护进程（即保证冗余又能保证数据库最终一致性，来源于鸽巢原理），保证写入的时候，不完全更新所有数据，但又在返回的时候保证返回给用户的数据是有效的

mogodb中使用replica set 技术，在分布式的情况下，把主机分为primary 和seccondprimary对外提供接口服务，当一个写入请求发送到primary中，primary节点，对请求进行解析，之后再分发给相应的second节点，各个节点通过定时发送heart beat进行同步。

其中quoram 机制，是保证高并发，和数据一致性的一个重要的机制。假如：当一份数据在分布式集群中，有存有三份，当写入数据的时候，不需要三份数据都要修改，只需要修改两份数据。当下一个读请求来的时候，只需要读取两份数据，在这两份数据中，一定存在至少一份数据是修改之后的数据。当这个原理推广到数据有N份冗余的时候，只需要在数据中，写入K个数据，当读的时候，读取N—K+1份数据的时候，那么必定至少有一份数据是更新后的数据。quoram机制，既能保证不完全更新，又能保证返回给用户的数据是有效的。

对MogoDB的自问自答

为什么在已经有mysql这种数据库的情况下，还会出现MogoDB这样的数据库？

1. MogoDB支持高并发------>mvvc，quoram等。而mysql在单节点上比较适合，当并发连接数量大了之后，性能就跟不上
2. 不需要大表连接 ------->mysql 大表连接性能差。在MogoDB中数据是noschema的并以文档的形式存储。这样就能尽可能的减少表连接操作提高相应速度
3. 可扩展--------->MogoDB既能横向扩展又能纵向扩展上，当10台机器，解决不了的时候，可以横向扩展。加到100台，1000台，也许整体执行效率不高，但是能合作解决以往传统数据解决不了的大数据量问题
4. 对于OLAP，aggregation操作，进行优化，提供了自己的语言来支持更高效率的map reduce操作。并且对json，sql都有比较好的支持
5. 同时提供full text search 和地理位置索引有很好的支持，这些在传统的面向对象的数据库中通常很弱

针对硬件发展优化的技术

memsql，meesql数据库的口号是sreaming transations analytics all in one system.针对流数据进行一站式开发
memsql是一种内存数据库。传统数据库，disk做主存，rammemory，做cache。memsql把memory作为主存。disk作为backup，或者journal使用，因为针对流数据，优化，所有数据只做顺序读写。充分利用存储金字塔。充分利用硬件，加快计算效率。在内存中，memsql采用行存储，并采用想skip-lists和hashtable这样的针对内存计算优化的数据结构加快计算。在disk中采用列存储结构。更高效的存储数据
而且memsql的驱动，与mysql完全兼容，针对程序员是透明的这一点在降低开发门槛很有效果。虽然memsql是一种内存数据库，但memsql在断电的时候，并不会丢失所有的数据，因为memory是主存，disk做backup和journal。在断电的时候任然能通过journal找回数据。是一种针对通用硬件，同事支持企业级应用的高性能内存数据库。支持完全的SQL
同事memsql可以设置持久化，并能很好的与spark等高性能计算平台进行集成成为实时计算的一种较好的选择

但memsql也有不适合的应用场景

1. memsql 不适合存储对象
2. 不适合低端硬件。官网建议最低的硬件 4core 8GB
3. 不适合作为共享DB(单节点安装)
4. 不适合作全文检索

memsql 自问自答

为什么有了mysql MogoDB 之后，还有memsql这款产品

1. 针对的应用场景不同，memsql针对流计算，更倾向与实时高性能计算，mysql，MogoDB更倾向与事务或者实时性要求不高的计算任务
2. 针对高性能计算采取了多种优化，如内存行存储。disk列存储。应用skip-list，hashtable等加快计算
3. 能与spark进行集成
4. 完全的SQL，能通过code genarationg加快，sql的运行

memsql与传统数据库相比，有什么优势

1. 可扩展，集成。能与spark深度集成
2. 基于流，无buffer pool （传统表数据库，在处理大数据量时候，假设不能完全放入内存中，内存设置buffer pool由DB和table共享，会产生竞争。导致争夺）
3. 采用lock-free技术最大化实现并发，用skip lists，或者hash table优化内存数据
4. code-genaration。lock-free技术的使用，使得解析动态sql的时候成为限制因素。所以对sql语句进行预编译。加快数据库运行。

数据库技术发展感悟

在今年上半年，看过的一篇文章《what comes around goes around》过去经历的，将来也会再一次到来。数据库，从最开始的树型结构，网状结构，星型结构，再到现在广泛使用的表结构。现在在大数据时代，于是，又出现了一些，例如MogoDB，这些文档型数据库。无疑感觉是一种轮回。

在数据库技术发展的历史过程中，我认为经历了这样的一些过程

1. 数据量大---》机器性能相对弱----》优先考虑性能
2. 程序员管理，苦不堪言----》性能低下
3. 机器性能提升，数据压力减小------》优先考虑程序员
4. 关系型数据库----》管理技术趋于统一-------》一统天下
5. 回到第一步

回顾数据库技术发展历史，数据从最初版本的用文件系统管理。然后出现了数据量大，使用文件系统管理效率太低，而且机器的性能这个时候又不够，这个时候考虑的是如何在有限的硬件条件下，如何把不能解决的问题尝试去解决。优先能不能处理的问题。就在这一时期，出现了树状结构，网状结构，星型结构。效率高了，以前不能解决的现在能够解决了。这是第一个阶段

第二个阶段。虽然数据是能解决了。但是随着数据管理技术的结构设计让程序员管理手动查询这个时候，对之前存在的遗留代码的管理操作。让后来的从业者苦不堪言。而且，最重要的是不同程度技术的程序员，写出的程序效率相差很大。这个时候，就会呼吁把数据管理，交给系统解放一部分程序员。

第三个阶段，随着机器性能的提升，计算机的广泛应用，越来越多的IT技术从业者。强烈要求妥协一部分性能。让广大普通程序员也能写出性能效率良好的管理工具，这个时候，出现了基于关系运算的数据处理技术，出现了给广大程序员提供一个统一的接口，而不用考虑数据库内部的运行过程。

第四各阶段，在这个时候。机器性能的提升，新理论的出现。利用机器性能提升的特点。关系型数据库似乎出现了一统天下的局面。之后，就是关系型数据库的广泛应用

第五个阶段。随着数据库越来越广泛的应用。数据积累的速度，也成指数性增长。于是又出现了类似第一阶段出现的问题，数据量大，机器性能相对弱

数据库技术，有10年理论，10年发展，10年应用的说法。我们现在所处的位置，似乎又回到了最初的数据量大，机器弱，优先考虑性能的这个阶段。观察，有些大数据管理系统如MogoDB，优先考虑性能，如，它会给用户暴露特定的针对MogoDB特有的编程规范，来加速系统的运行。这就类似于程序员手动管理。

这是一种，用人力，换取效率的过程。带来的提升就是，以往不能解决的问题，现在能够解决了。但是不久就会出现，维护不变，市场需求量大。广大程序员需要一种，效率不那么极致，但是能解决大部分问题的管理技术。未来，数据库管理技术，会逐渐从零散到统一。从少量使用，到大量使用，最后又出现性能不够处理的情况。

每一个轮回都是一次管理技术的提升。每一次硬件的效率提升，都会带来新一次的变革。有的变革是理论驱动。有的变革，是硬件技术上的提升

参考地址：
http://www.dongcoder.com/detail-300824.html