《数据库核心技术学习报告》由会员分享，可在线阅读，更多相关《数据库核心技术学习报告（28页珍藏版）》请在金锄头文库上搜索。
1、贵州大学数据库核心技术学习报告非关系数据库与关系数据库异同报告高级数据库课程报告2015021593 黄天驰目录1引言22内部数据结构42.1 string VS simple dynamic string(sds)42.2顺序索引 & b+树VS 跳跃表62.2.1稠密索引62.2.2稀疏索引72.2.3 B+树82.2.4跳跃表92.3 B+树码压缩 VS 压缩列表152.3.1 B+树码压缩152.3.2 压缩列表162.4 整数集合193 数据测试224 小结255 附录274.1引用文献：271引言在进入研究生学习之前，我曾经和小伙伴们共同开发了一款游戏这款游戏有非常高的实时性，基本
2、要与服务器长连接并不断交换数据。然而，这些实时交换的数据并不是数据库想去记录的他们是动态数据，可能并不需要保存在数据库里，甚至数据库不需要去知道这些东西。可能在游戏完成后，我仅仅需要保存他的成绩进入数据库即可。但是，我可能又需要了解这些所谓的脏数据，毕竟他可能记载了大部分玩家的行为，作为我来说这是优化游戏，让游戏变得更加好玩的关键点。说到底，就是高并发，高实时性的脏数据。最初，在我构建的游戏服务器grandserver中选择了mysql作为记录所有数据的服务器，包括静态数据和动态数据。起初，一切一帆风顺，所有操作在封装的协议中顺利交互。但是到了游戏制作，也就是数据频繁交互的阶段，我总是比预想中
3、更晚收到我想要的指令，或者说，两者交互时间非常晚。在查询mysql记录时发现，我总是不停的在改一整张表。效率跟不上后，我放弃了mysql，在仔细甄选后，选择了nosql技术中的redis作为数据库缓存服务器。随后我的代码被封装了成了图1-1：在使用该类调用脏数据操作后，通过lua层的简单交互，终于让数据变得正常。但是当时我在做完解决方案后留下了几个问题，还未解决即准备考研。问题如下：l nosql盛行的时代，sql存在的意义。l nosql甚至可以在增加一个sql语句解释器的情况下完全变为sql数据库，那sql的存在意义到底在哪里。经过将近半年的学习，在了解了双方内部的操作与区别后，我个人认为
4、双方各有所长。本文以sqlite与redis中的数据结构的异同点为出发点，着重分析sql和nosql架构中的区别以及他们不可替代的地方。#pragma once#include extern C#include hiredis.husing namespace std;class mythRedisKeypublic:int toint();string tostring();mythRedisKey(redisReply* reply);mythRedisKey();void release();private:redisReply* _reply;/void release();图1-12
5、内部数据结构2.1 string VS simple dynamic string(sds)在大多数开源关系数据库中并没有对最基本的string进行优化，很多数据库例如sqlite甚至直接使用了const char*来作为基本数据库的string结构作为储存结构。故很多时候在不同系统上更加依赖类似strlen的处理效率。而在Redis没有直接使用 C 语言传统字符串表示（以空字符结尾的字符数组，以下简称 C 字符串），而是自己构建了一种名为简单动态字符串（simple dynamic string，以下简称SDS）的数据结构，并将 SDS 用作 Redis 的默认字符串表示。 在 Redis
6、里面，C 字符串只会作为字符串字面量（string literal）用在一些无须对字符串 值进行修改的地方，比如打印日志： redisLog(REDIS_WARNING,Redis is now ready to exit, bye bye.);当Redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis 就会使用 SDS 来表示字符串值，比如在 Redis 的数据库里面，包含字符串值的键值对在底层都是由 SDS 实现的。每个sds.h/sdshdr结构表示一个 SDS 值，如图2-1： / 记录buf数组中已使用字节的数量struct sdshdrint len;
7、/ 等于SDS所保存字符串的长度int free; / 记录buf数组中未使用字节的数量char buf;/ 字节数组，用于保存字符串;图2-1如图2-2展示了一个 SDS 示例：图2-2 free = 0，表示这个 SDS 没有分配任何未使用空间。 len = 5，表示这个 SDS 保存了一个五字节长的字符串。 buf属性是一个char类型的数组，也就是普通的c语言string类型数组。他的前五个字节分别保存了R,e,d,i,s五个字符，而最后一个字节则保存了空字符0。 SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS 的 len属性里面，并且为空字符分配额外
8、的1字节空间，以及添加空字符到字符串末尾等操作，都是由 SDS 函数自动完成的，所以这个空字符对于 SDS 的使用者来说是完全透明的。所以遵循空字符结尾这一惯例的好处是，SDS 可以直接重用一部分 C 字符串函数库里面的函数。这么做的好处非常显而易见，和 C字符串不同，因为 SDS 在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O(1)。故可以总结出比起C字符串，SDS具有以下优点：l 常数复杂度获取字符串长度。l 杜绝缓冲区溢出。l 减少修改字符串长度时所需的内存重分配次数。l 二进制安全。l 兼容部分C字符串函数。2.2顺序索引 & b+树VS 跳跃表在关系数据库
9、中为了快速访问随机文件中的记录，一般使用顺序索引。每一个索引结构与一个特定的搜索码相关联。顺序索引按照顺序存储搜索码的值，并且将每个搜索码与包含该搜索码的记录连接起来。被索引文件中的记录自身也可以按照某种排序顺序存储。一个文件可以有许多个索引组成，分别基于不同的搜索码。如果包含记录文件按照某个搜索码指定的顺序排序，那么该搜索码对应的索引称为聚集索引或主索引。搜索码指定的顺序与文件中记录的物理顺序不同的索引即为非聚集索引或者辅助索引。如图2-3例子所示：用户ID用作搜索码，记录按照该搜索码顺序存放。索引记录根据数据记录的稠密程度分为稠密索引和稀疏索引UserIDUserNameUserPwdRe
10、alNameFullControl1rootpassroot31012test001test001test0012101312312312321003sonysonysony21004test2test2test2210092222222222101011121014testtesttest21016222198123456222198210172221911234562221912图2-32.2.1稠密索引如果记录是排好序的，我们就可以在记录上建立稠密索引，它是这样一系列存储块：块中只存放记录的键以及指向记录本身的指针，指针就是一个指向记录或存储块地址。稠密索引文件中的索引块保持键的顺序与文
11、件中的排序顺序一致。既然我们假定查找键和指针所占存储空间远小于记录本身，我们就可以认为存储索引文件比存储数据文件所需存储块要少得多。当内存容纳不下数据文件，但能容纳下索引文件时，索引的优势尤为明显。这时，通过使用索引文件，我们每次查询只用一次I/O操作就能找到给定键值的记录。稠密索引支持按给定键值查找相应记录的查询。给定一个键值K，我们先在索引块中查找K。当找到K后，我们按照K所对应的指针到数据文件中找到相应的记录。似乎在找到K之前我们需要检索索引文件的每个存储块，或平均一半的存储块。然而，由于有下面几个因素，基于索引的查找比它看起来更为有效：1. 索引块数量通常比数据块数量少。2. 由于键被
12、排序，我们可以使用二分查找法来查找K。若有n个索引块，我们只需查找log2n个块。3. 索引文件可能足够小，以至可以永久地存放在主存缓冲区中。要是这样的话，查找键K时就只涉及主存访问而不需执行I/O操作。2.2.2稀疏索引稀疏索引只为数据文件的每个存储块设一个键-指针对,它比稠密索引节省了更多的存储空间，但查找给定值的记录需更多的时间。只有当数据文件是按照某个查找键排序时，在该查找键上建立的稀疏索引才能被使用，而稠密索引则可以应用在任何的查找键。如图2所示，稀疏索引只为每个存储块设一个键-指针对。键值是每个数据块中第一个记录的对应值。在已有稀疏索引的情况下，要找出查找键值为K的记录，我们得在索
13、引中查找到键值小于或等于K的最大键值。由于索引文件已按键排序，我们可以使用二分查找法来定位这个索引项，然后根据它的指针找到相应的数据块。现在我们必须搜索这个数据块以找到键值为K的记录。当然，数据块中必须有足够的格式化信息来标明其中的记录及记录内容。2.2.3 B+树关于b+树这个经典数据结构在此无需赘述，如图2-4给出典型的3阶B+树示例。通过这张图我们能很轻松找到他的特性：1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；2. 不可能在非叶子结点命中；3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；4. 更适合
14、文件索引系统；图2-4B+树的基本操作总结如下所示：查找操作对B+树可以进行两种查找运算：a.从最小关键字起顺序查找；b.从根结点开始，进行随机查找。在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。插入操作B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。删除操作B+树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非
15、终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 （m/2结果取上界，如5/2结果为3）时，其和兄弟结点的合并过程亦和B-树类似。当然，B+树更适合做文件索引和数据库索引的原因是B+树的磁盘读写代价更低，同时B+树的查询效率更加稳定。2.2.4跳跃表在redis中，代替b+树的是跳跃表。跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。Redis使用跳跃表作为有序集合键的底层实现之一，如果一
