数据库（三），底层算法
本文主要整理了数据库常用的算法。
我们虽然没有必要从头开始了解数据库的底层算法是什么，但是了解大概原理是必要的。
其实现在很多技术都可以从经典算法中找到原型，比如Hadoop其实就是合并算法演变过来了。
这样说来算法相当于内功，如果能理解了这些算法，再学其他的技术，就是一鞭一条痕 一掴一掌血
在了解所有算法之前，需要先了解算法复杂度，这里的算法复杂度主要指的是时间复杂度，是当数据量增加时运算如何增加的一种度量。相当于给算法一把标尺，这样我们才好比较那种算法更优。同时当数据量已经到了海量的级别，我们必须尽可能的扣性能，这样才能保证整个架构的可用性。
算法复杂度
这里的复杂度主要指的算法的时间复杂度，是当数据量增加时运算如何增加。
下图标识了几种常用算法的复杂度，我们可以有个直观的认识。
image.png
面临海量数据时
- 哈希表：O(1)
- 搜索均衡树:O(log(n))
- 搜索阵列：O(n)
- 最好的排序算法O(n*log(n))
- 糟糕的排序：O(n^2)
正因为哈希表、均衡树以及好的排序算法的时间复杂度是这个样子，我们才会选用它。
image.png
常用排序算法:合并排序
原理
数据库里面最常用的排序算法莫过于合并排序，它主要用在对查询优化、数据库联接上。
假设现在给了我们两个数量为4的序列，要把他们按照从小到大的顺序合并成一个8元素的序列，应该怎么做。
可以双方都出一个元素过来比较，谁小则放到8元素序列中。比如下图中：
- 第一轮：1比2小，所以把1放到序列中。
image.png
-
第二轮：左边的1已经放到下面去了，右边的2还没有动。所以要比较的是3和2，当然2小 。
image.png
-
第三轮：比较3和4
image.png
-
重复
全部过程可以看如下的Gif
[图片上传失败...(image-caadf4-1517988116119)]
总结一下：
- 比较当前元素，所谓当前元素，指的是序列中的第一个。
- 小的元素放入8元素序列
- 继续比较
仔细看上面的算法，是不是两个序列合并之后就成了有序的呢。
不过要执行这种算法，有个必要条件是要合并的序列必须是有序的，这样才可以只比较当前元素完成排序。
但是对任意一个序列来说不可能是完全有序的。那么此时就陷入了僵局。
那么我们可不可以这样想，单个元素肯定是有序的吧，所以我们如果把两个1元素的序列合并，肯定是可以用这种算法的，这样就得到一个2元素的有序序列，如果此时还有一个2元素的有序序列，是不是可以再合并。然后是4元素序列合并，接下来是8元素序列合并。
大概是下图这个样子
image.png
那要怎么得到这样1元素的序列呢？当然是拆分。8元素拆分为4，4拆分为2，拆分为1 。
好了，这个算法就完整了。
首先为了获得1元素的序列 ，我们需要把要排序的序列进行拆分，拆分以后再进行合并。
- 拆分阶段，将序列分为更小的序列
- 排序阶段，把小的序列合在一起（使用合并算法）来构成更大的序列
拆分阶段
image.png
使用3个步骤将序列分为一元序列。步骤数量的值是 log(N) ,比如现在是 N=8, log(N)=3
为什么呢？因为拆分的每一步都是把原序列长度除以2，所以要执行多少步就是能把原序列除2多少次，正好就是对数的定义嘛。
排序阶段
image.png
同样，排序阶段也有log(N)个步骤，理由与上面拆分阶段的相同。
而每次个步骤，所有的元素都需要动一下才能移到下一个序列里面，所以每个步骤都需要执行N次运算。
也就是说整体成本是 Nlog(N) 次运算。*
完整过程如下：
[图片上传失败...(image-296b65-1517988116119)]
合并排序的应用
如果熟悉Hadoop就知道，里面的MapReduce其实就是这种思想，分而治之，把一个大的任务拆分成若干小的任务，最后再各个击破，合并即可。
可以说MapReduce就是合并算法修改后的结果，它可以运行在多处理、多服务器这种架构上罢了。
image.png
常用数据结构
数组
说到数据库的数据结构，我们最容易想到就是的类似于Excel那样的数据表了。
如下图
image.png
每一行表示一个主体，而每一列则是若干属性或者说叫字段。
优点是非常的直观，缺点是太过简单，当数据量太大的时候，查找不易。
那么为了优化查找，主要有两种方法一是构建查找树，一是Hash表。下面我们分别介绍。
树
如果直接在数组或者阵列上进行查找，而且如果碰巧它又是有序的，自然好办，可以使用折半、插值等方法。但是实际上，大部分的数组不大可能是有序的，所以需要在进行排序，需要消耗大量的资源和时间。
那么有没有办法可以插入和删除效率还不错，而且又比较高效的进行查找呢？
如果我们束手无策的话，不妨从最简单的情况入手，如果现在只有{62}，然后需要把88插入进来，就成了{62,88}，如果现在要插入58，同时还保持有序，自然需要把88往后挪一下。可以不挪吗？
我们知道树这种结构，可以方便的插入和删除，然后引伸出二叉树结构了。
首先将62定为根结点，88比62大，所以做为62的右子树，同理，58成为左子树。
image.png
下图就是一棵二叉排序树，只要对它进行中序遍历就可以获得一个有序的序列
image.png
比如此时我们要查询93，则可以像下面一样查询。
image.png
我们只要查到了93，就可以知道它再哪一行，然后在这一行里面去查找，范围自然小了许多。
那么查询的成本呢？自然就是树的层数，即$log(N)$
那么设想这样一个例子。
如果数据库中的一张表含有一个country的字段，现在要找谁在China工作。如果是阵列的话，我们需要将整张表都扫一下
但是如果把country字段中所有的元素建立一个二叉查找树，则最多使用$log(N)$就可以查找代表China的节点，然后通过这个节点就知道有哪些行需要考虑了。
这就是索引，索引就是用其他的数据结构来表示某些列，可以加速对此列的查找。
但是新的问题又来了，查找某个值用二叉查找树挺好的，但是如果要查找两个值之间的多个元素怎么办？使用二叉查找树需要查找每个树的节点才能判断是否在两个值之间。
于是我们引入了一种改进的树——B+树
其特征为：
- 只有叶节点才保存相关表的行位置信息
- 其他节点只是用来指路的，也就是在搜索中指引到正确的节点而已。
image.png
可以看出，多了一整行用来保存信息的，此时如果要找40~100之间的值，
只需要先找到40，然后遍历后续节点即可。
比如找了M个后续节点，则需要$M+log(N)$次即可。
但是B+节点需要保持顺序，如果在数据库里面增加或者删除一行，则需要B+树进行较大的变化，查入和删除也是O(logN)复杂度的。
所以索引不能太多，它会减慢插入、更新、删除行的操作。
image.png
Hash
前面说过使用Hash表进行查找，其时间复杂度只有O(1)，应该是最快的查找方法了。
不管是普通的序列还是顺序表，我们都需要拿要查找的值与序列中的元素进行比较，那么能否只根据关键字key就能查找到对应的内存位置呢？
也就是存在这样一种函数：
$$存储位置 = f (关键字)$$
这就是所谓的散列技术，这个 $f$就是散列函数，又称为哈希函数。
采用散列数据将记录存储在一块连续的空间里面，这块空间就叫散列表或者哈希表。
存储的时候，通过散列函数可以计算记录的散列地址，并按照此地址进行存储。
在查找的时候，也同样使用此散列函数计算相应的地址进行查找。
也就是在哪存的就去哪找，那么散列技术既是一种存储技术，又是一种查找技术
散列技术最适合的场景是查找与给定值相等的记录。因为不需要比较，效率大大提高。
但是如果遇到一个key对应多条记录，就不适合用散列表了。比如使用关键字“男”去查找一个班的学生，明显是不合适的。
同样，散列表也不适合范围查找，也就是查找40~100学号的同学。
另外，我们还会经常遇到两个关键字使用散列函数却得到同样的地址，这样就冲突了，可以可以把这个key称为散列函数的同义词，所以还需要设计方法来避免冲突。
构造哈希函数
上面说过一个好的哈希函数最关键的是让散列地址均匀的分布在存储空间里面，这样可以减少冲突，一般来说常用的散列函数都是将原来的数字按照某种规律变成另一种数字的。
-
对数字进行抽取。如果我们获得的数字都是很长一串，也就是key的位数很大，而且里面若干位比较平均，可以将其抽取出来，进行反转、右环位移等等让关键更为平均。
也就是说这里面的散列函数实际上是抽取关键字的一部分。
比如手机号，就可以抽取其中几位
image.png
- 如果不知道关键字的分布，位数又不大，可以进行平方，然后取中间3位做为散列地址。比如1234，平方就是1522756，取中间3位227作为散列地址。
- 上面说的都有点特殊，实际上最常用的是对key进行取模，或者说对关键字进行平方取中、折叠后再取模
$$f(key)=key \qquad mod \qquad p (p<=m)$$
那么如果$p$选得不好，冲突就会比较多了。
根据经验，如果表长为$m$，则$p$为小于或等于$m$的最小质数或不包含小于20质因子的合数。
解决冲突
解决冲突我们只介绍一种，就是链地址法
我们可以将所有关键字为同义词的记录存储在一个单链表中，这样每个链表就叫哈希桶
所以散列表只存储所有同义词子表的头指针，这样无论有多少冲突 ，只需要在当前位置给单链表增加结点。
image.png
那么一个好的哈希函数应该让哈希桶里面的元素非常少才对，这样就可以直接在表里面查找到，时间复杂度为O(1)
image.png
