在我们理解了隐藏在时间复杂度和排序后面的思想之后，我必须再谈谈3种数据结构了。它们极其重要，因为它们是现代数据库的基石。我也会顺便介绍下索引的概念。 数组 二维数组是最简单的数据结构，一张数据库表就可以看做一个二维数组，例如： 二维数组就是一
在我们理解了隐藏在时间复杂度和排序后面的思想之后，我必须再谈谈3种数据结构了。它们极其重要，因为它们是现代数据库的基石。我也会顺便介绍下索引的概念。
二维数组是最简单的数据结构，一张数据库表就可以看做一个二维数组，例如：
二维数组就是一个既有行又有列的表：
虽然表能很好的存储并展示数据，但是当你需要搜索数据时，它的表现就很糟糕了。
例如，如果你要找到所有的英国朋友，你就必须查看每一行数据，然后判断他/她是否是英国人。这会耗用N个操作（N表示行的数量），虽然看起来也并没有多糟糕，可是让我们想想，有没有更好的方法呢？答案就是树。
注意，大部分现代数据库都会提供高级数组便于更高效的存储表，比如：基于堆、基于索引。但这样，也并没有解决在特定条件下快速搜索的难题。
一个二叉搜索树就是一个具有特定属性的二叉树，每个节点都满足下列属性：
让我们用图来更直观的说明二叉搜索树：
上图中的树包含15个节点，让我们来搜索值为208的节点：
让我们换一个值来搜索，比如40：
最终搜索耗费的操作就是树的高度。如果你认真的阅读了之前关于归并排序的章节，你应该能够推断实际操作数就是log(N)，不错的效果咯！
上边我们描述的都是节点值是整数的简单场景，那么如果我们的节点值不是整数怎么办呢？想想一下上表中的每个人的国籍，都是字符串类型。假设你有一个值为国籍的树：
整个搜索过程耗费了log(N)次操作，而不是使用数组时的N次。上边的过程，实际就是通过数据库索引查找指定行的过程。
一旦拥有比较列值的函数，你就可以对任何类型的列进行排序，同时意味着你可以构造一棵索引树。（译者注：关键是能够比较列值，否则没法排序）
下一章节我们继续介绍非常非常非常（译者注：重要的事情说三遍）重要的B+Tree索引。
