数据结构 二叉树遍历 关系型工作原理

通过前面的章节， 我们已经理解了时间复杂和归并排序的概念，接下来我要介绍三种数据结构。这三种数据结构非常重要，它们是现代系统的基石。我也会讲一讲索引的概念。

二位数组是一种最简单的数据结构，一张表就可以看成是一个二维数组。例如：

这个二维数组就代表一张有行和列的表结构：

每一行代表一个对象

每一行所有列的数据代表了一个对象的所有属性

每一列固定存储某一种类型的数据(如：integer、string、date…)。

尽管，二维数组用于存储表数据非常好，但是当你需要从数组中根据某个条件查询数据时，性能无法接受。

例如：你想找出在英国工作的所有人，你需要遍历每一行数据，判断他是否属于英国。这个过程需要执行N步操作(N取决于表的行数)。听起来，性能也不算太差，但有更快的方法吗？

肯定有，接下来就应该树结构登场了。

备注：现代使用更高级的数组结构来存储表数据，如heap-organized tables或者index-organized tables。但是都没有解决如何在数组中根据一些列的过滤条件快速筛选数据的问题。

这棵树有15个节点。我们看一下如何从中找到208这个元素：

从根节点开始查找,根节点是136。因为 136<208，所以在136的右子树中查找。

398>208，在398的左子树中继续查找。

250>208，在250的左子树种继续查找。

200<208，在200的右子树中查找。但是200没有右子树。没有找到208(因为如果能找到的话，它应该在200的右子树上)。

接着看一下如何查找40这个元素：

也是从根节点136开始查询。因为136>40，所以在136的左子树中查询。

80>40，在80的左子树中查找

40=40, 元素找到了！提取40这个节点中存储的对应数组的行号索引。

有了这个行号索引，想拿这行的数据，就能立即获取到(数组的下标访问)。

最终，两次查询的操作步骤数都是树的高度。如果，你仔细阅读过merge sort章节，应该知道树的高度是log(N)，所以该查找算法的时间复杂度是O(log(N))。还不错。

文章内容非常抽象，让我们回到问题上来。除了简单的整数型数据，考虑一下字符串，它是用于在前面的表中表示某个人的所属国家信息的。假设，你已经构建了一个树，包含前面表中的“country”字段数据。

你想知道哪些人在UK工作

你需要查找树，找到UK的节点。

在UK节点内，你能找到所有在UK工作人的对应数组行号索引信息。

这个查询操作仅耗费了Log(N)步操作，而不是直接在数组中查询所需要的N步。现在你也能猜到索引是什么东西了吧？

你能为任意多列数据建立索引(一列字符串，一列整型数，2列字符串，一列整型 + 一列字符串，一列日期类型等等)。只要你对这些列实现了比较函数，你就能控制主键在树中的排列顺序(已经为基本数据类型实现了比较函数)。

尽管上面的二叉树在查询某个固定值时工作得很好，但是如果要查询某个范围内的所有数据，性能就非常低。它需要花费N步操作，因为需要比较树中的每一个节点以判断它是否在指定的范围内。数据结构 二叉树遍历此查询方法(range query)。为了解决这个问题，现代使用B+树，B+树是前面二叉查询树的优化。在B+树里面：

只有叶子节点存储关联表的每一行数据对象的指针(译者注：这里的指针是指能快速找到数据本身的数组行号，哈希表的key等索引，不仅是C 语言中的pointer， 下同)。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-74529-1.html