如果再有人问你数据库的原理，把这篇文章给他( 二 ) _数据库

O(n) 算法会消耗 2000 次运算

O(n*log(n)) 算法会消耗 14,000 次运算

O(n^2) 算法会消耗 4,000,000 次运算

O(1) 和 O(n^2) 的区别似乎很大（4百万）,但你最多损失 2 毫秒，只是一眨眼的功夫。确实，当今处理器每秒可处理上亿次的运算。这就是为什么性能和优化在很多IT项目中不是问题。
我说过，面临海量数据的时候，了解这个概念依然很重要。如果这一次算法需要处理 1,000,000 条元素（这对数据库来说也不算大）。

O(1) 算法会消耗 1 次运算
O(log(n)) 算法会消耗 14 次运算
O(n) 算法会消耗 1,000,000 次运算
O(n*log(n)) 算法会消耗 14,000,000 次运算
O(n^2) 算法会消耗 1,000,000,000,000 次运算

我没有具体算过，但我要说，用O(n^2) 算法的话你有时间喝杯咖啡（甚至再续一杯！）。如果在数据量后面加个0，那你就可以去睡大觉了。
继续深入
为了让你能明白

搜索一个好的哈希表会得到 O(1) 复杂度搜索一个均衡的树会得到 O(log(n)) 复杂度搜索一个阵列会得到 O(n) 复杂度最好的排序算法具有 O(n*log(n)) 复杂度糟糕的排序算法具有 O(n^2) 复杂度

注：在接下来的部分，我们将会研究这些算法和数据结构。
有多种类型的时间复杂度

一般情况场景
最佳情况场景
最差情况场景

时间复杂度经常处于最差情况场景。
这里我只探讨时间复杂度，但复杂度还包括：

算法的内存消耗
算法的磁盘 I/O 消耗

当然还有比 n^2 更糟糕的复杂度，比如：

n^4：差劲！我将要提到的一些算法具备这种复杂度。
3^n：更差劲！本文中间部分研究的一些算法中有一个具备这种复杂度（而且在很多数据库中还真的使用了）。
阶乘 n：你永远得不到结果，即便在少量数据的情况下。
n^n：如果你发展到这种复杂度了，那你应该问问自己IT是不是你的菜。

注：我并没有给出『大O表示法』的真正定义，只是利用这个概念。可以看看维基百科上的这篇文章。
合并排序当你要对一个集合排序时你怎么做？什么？调用 sort() 函数……好吧，算你对了……但是对于数据库，你需要理解这个 sort() 函数的工作原理。
优秀的排序算法有好几个，我侧重于最重要的一种：合并排序。你现在可能还不了解数据排序有什么用，但看完查询优化部分后你就会知道了。再者，合并排序有助于我们以后理解数据库常见的联接操作，即合并联接。
合并
与很多有用的算法类似，合并排序基于这样一个技巧：将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并。
我们用个简单的例子来看看这是什么意思：