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