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

其它节点的用途只在查询的时候，帮助路由到想找的叶子节点。数据结构 二叉树遍历

如上图所示，B+树存储了更多冗余的节点(2倍)。树内部多出了一些附属节点，这些“decision nodes”的作用是帮助你找到正确想要的叶子节点(存储了表数据指针的节点)。B+树的查询时间复杂度仍然是Log(N), 树仅仅只是多出了一层。最大的差异是，叶子节点中存储了指向下一个节点的指针。

在这个B+树里面，如果你查找40到100之前的数据：

你只需要查询值为40的节点(或者比40稍大的节点，如果40的节点不存在的话)。查询方式跟之前的二叉树一样。

收集40后继的节点，通过它存储的指向后继结点的指针，直到遇到100(或者比100少大的数).

假如，你需要查询M个节点，树有N个节点。查询指定的值(40)的时间复杂度是Log(N), 跟之前的二叉树查询一样。但是，一但你找到了节点(40)，你还需要通过M步操作，遍历收集M个后继结点。B+的range query的时间复杂度是O(M+Log(N)), 相比之前二叉树O(N)复杂度，性能提升很多。数据量越大，性能提升越明显。你不需要读取整颗树，这也意味着更小的磁盘I/O读取。

但是，这也带来了新的问题(再一次遇到问题)。如果你往添加或者删除一行记录，同时也需要在B+树中更新数据：

你需要保证B+树中的节点顺序，否则你无法在一个混乱的树中查找节点。

你必须要保证叶子节点的从小到大的顺序排列，否则range query的时间复杂度将由O(Log(N))退化为O(N)。

换句话说，B+树必须要有自我调整树平衡性和节点顺序的能力。谢天谢地，智能化的数据删除和数据插入操作使得B+树的能保持以上特征。这也带来了成本：插入和删除数据的时间复杂度是O(Log(N)), 这也是为什么你经常会听到这样一种观点：索引太多不是什么好事。实际上，这会降低插入/更新/删除操作的效率，因为需要同时更新表的索引，每个索引花费O(Log(N))的时间。

译者注：凡事都有两面，有利必有裨；选择什么样的数据结构，是根据你的应用场景来的。

另外，索引也会增加tansaction manager的复杂度(最后一张将讲到tansaction manager)。

更多的细节，你可以在维基百科上搜索B+ Tree。如果你想要一个B+树实现的样例，你可以读一下这篇文章(https://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/), 这篇文章的作者是MySQL的核心开发人员。他详细讲述了innoDB(MySQL引擎)是如何实现索引的。

最后一个重要的数据结构是hash table。当你需要快速查找一个数据时，hash table非常有用。另外，理解了hash table将帮助我们理解后面将提到的一种常用连接技术：hash join。Hash table也经常用于存储一些的内部管理数据，如lock table，buff pool等。这些概念在后面都会讲到。

Hash table是一种能根据关键字快速查找数据的数据结构类型。构建hash table需要定义如下一些内容：

1) 对象关键字

2) 为关键字定义的哈希函数(hash function)。对象的关键字用哈希函数计算的结果表示了对象存储的位置(称为buckets)。

3) 关键字比较函数。一旦找到了对象所在的bucket，接下来需要在bucket内部，通过比较函数找到对应的对象。

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