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

文章插图

在拆分阶段过程中，使用3个步骤将序列分为一元序列。步骤数量的值是 log(N) （因为 N=8, log(N)=3）。【译者注：底数为2，下文有说明】
我怎么知道这个的？
我是天才！一句话：数学。道理是每一步都把原序列的长度除以2，步骤数就是你能把原序列长度除以2的次数。这正好是对数的定义（在底数为2时）。
排序阶段

文章插图

在排序阶段，你从一元序列开始。在每一个步骤中，你应用多次合并操作，成本一共是 N=8 次运算。

第一步，4 次合并，每次成本是 2 次运算。
第二步，2 次合并，每次成本是 4 次运算。
第三步，1 次合并，成本是 8 次运算。

因为有 log(N) 个步骤，整体成本是 N*log(N) 次运算。
【这个完整的动图演示了拆分和排序的全过程，不动戳大。】

文章插图

合并排序的强大之处
为什么这个算法如此强大？
因为：

你可以更改算法，以便于节省内存空间，方法是不创建新的序列而是直接修改输入序列。

注：这种算法叫『原地算法』(in-place algorithm)

你可以更改算法，以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O 。方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时，这是个很重要的技巧。

注：这种算法叫『外部排序』(external sorting) 。

你可以更改算法，以便于在多处理器/多线程/多服务器上运行。

比如，分布式合并排序是Hadoop（那个著名的大数据框架）的关键组件之一。

这个算法可以点石成金（事实如此！）

这个排序算法在大多数（如果不是全部的话）数据库中使用，但是它并不是唯一算法。如果你想多了解一些，你可以看看这篇论文，探讨的是数据库中常用排序算法的优势和劣势。
阵列，树和哈希表既然我们已经了解了时间复杂度和排序背后的理念，我必须要向你介绍3种数据结构了。这个很重要，因为它们是现代数据库的支柱。我还会介绍数据库索引的概念。
阵列
二维阵列是最简单的数据结构。一个表可以看作是个阵列，比如：

文章插图

这个二维阵列是带有行与列的表：

每个行代表一个主体
列用来描述主体的特征
每个列保存某一种类型对数据（整数、字符串、日期……）

虽然用这个方法保存和视觉化数据很棒，但是当你要查找特定的值它就很糟糕了。举个例子，如果你要找到所有在 UK 工作的人，你必须查看每一行以判断该行是否属于 UK。这会造成 N 次运算的成本（N 等于行数），还不赖嘛，但是有没有更快的方法呢？这时候树就可以登场了（或开始起作用了）。
树和数据库索引
二叉查找树是带有特殊属性的二叉树，每个节点的关键字必须：