3.数组.树.哈希表
这一节讲数据结构。很重要，因为它是现代数据库的主心骨。在这一节，我还会介绍数据库索引的概念
3.1 数组
二维数组是一种最简单的数据结构，一个表可以看作是一个数组，例如：
这个二维数组是一张行和列组成的表：
- 每行代表一个主题
- 这些列描述主题的功能
- 虽然可以很好地存储和可视化数据，但是当您需要查找特定值时，它会很糟糕。 例如：如果你想找到所有UK工作的人，你只能查找每一行去确定是不是有UK工作的，这将花费你N次操作（N=行数）,这也不太差但这里有更快的办法吗？这就是一会我们要说的”树”出现了。
Note: 大多数现代数据库都提供高级阵列来高效地存储表，例如堆组织表或索引组织表。 但这并不会改变在一组列上快速搜索特定条件的问题。
3.2 树和索引
二叉搜索树是一种有特殊属性的二叉树，每个节点中的key必须满足以下条件：
- 必须大于所有存储在左侧子树中的key
- 必须小于所有存储在右侧子树中的key
让我们用图看看这个意思
这棵树有N=15个元素,我们来试试找 208
- 我从根节点 136 开始. 因为136<208, 我需要在136的右子树上找.
- 398>208 因此, 我要找398的左子树
- 250>208 因此, 我要找250的左子树
- 200<208 因此, 我要找200的右子树. 但 200 并没有右子树, 这个KEY不存在 (因为如果它存在,它只能存在200的右子树上,现在没有)
我们来试试找 40
- 我从根节点 136 开始. 因为136>40, 我需要在136的左子树上找.
- 80>40 因此, 我要找80的左子树
- 40= 40, 节点存在. 我提取出这个节点行id(图上没有显示ID)然后通过行id查找表
- 知道行ID后，我便知道数据在表上的确切位置，因此可以立即获取它。
最后,两个搜索都花费了*树的高度*次操作,如果你有认真阅读上一节中我们关于合并排序的内容 ,你应该明白这个值是 log(N).所以花费了long(N)次操作.还不错!
3.3 回顾下我们的问题
但是这个描述非常抽象,让我们回到我们的问题(上一小节中在表中查找UK工作的人). 同样是一棵树,不过这次不再是愚蠢的int型数字,而是一个代表国家的字符串. - 如果你想知道都有谁在UK这个国家工作 - 你查找这棵树得到UK所在的节点 - 在UK这个节里,你将发现对应的ROWS的地址 这次查找工作只花费了你log(N)次操作,比起直接扫描列表的方法用的N次.你刚才用的方法就是一个数据库索引
你可以对任何一组列建索引(一个string ,一个int,2个string ,1个int+1个string,一个date ….) 只要有一个可以函数可以处理这个KEY的长度,才便于你建立和排序这些KEY .
3.4 B+树索引
尽管这个树(二叉搜索树)可以很好的找到指定值 ,但是这里有个大问题:当你需要找到两个值之间的多个元素.它会花费O(N)因为你需要扫描树上的每个节点以检查是否符合这个条件(树的有序遍历),而且这个操作对磁盘IO不友好,因为要读整个树.我需要找一个方法提高范围查询的效率.为解决这个问题,现代的数据库采用了一个刚才说的二叉搜索树的修改版版本叫做B+树.在一个B+树上 - 只有最底层的节点(叶子节点)存储信息(一般是行在对应表中的具体位置) - 其他节点只是为了搜索中路由到正确节点存在的
如你看到的那样,这里有更多的节点(两倍多),事实上,你需要额外的节点,这些”判断节点”将帮助你找到正确的节点(存了真实的数据表行位置信息).但这个搜索的复杂度还是O(log(N))只是多了一个层级.最大的不同是最下面的叶子节点链接了它的下一个节点.
在这个B+树上,如果我们要找到40到100的值: - 你只需要像刚才二叉树上一样的方式找到40(如果40不存在就找到比40大的最小的数) - 然后顺着下一个叶子的链接一直收集直到100. 对比下从这个N个节点的树上找到了M个节点.这个找符合条件的40像上棵树一样花费了log(N).但是,一旦找到了这个节点,只需要M次操作就得到了所有需要的M个节点.所以这个搜索只花了M + log(N)次操作,对比上一个搜索树的N次.而且,不需要读整个树(只需要M+LOG(N)个节点),这就意味着更少的磁盘占用,如果M的数目不大(比如说200行)N的数目大(100万行)这里将差跟很大.
但是这里有个新问题(又来!).如果你在数据库增加或删除一行数据(如果这行数据在关联的B+树中): - 你需要维持B+树上的这些节点的顺序,否则你就不能在这些混乱的节点找到你需要的那些节点 - 你需要维持B+树尽可能低的层级,否则这个时间复杂度的 O(log(N)) 将变成 O(N).
换句说说,B+树需要自排序和自动平衡.还好聪明的删除和插入动作可以解决这个问题.但是这也是有代价的:B+树上的插入和删除动作O(log(N)).这也是为什么你们会听说用太多索引不是个好主意.确实,你正在降低表中insert/update/delete操作的速度,因为数据库需要更新这张表的所有索引,每个索引需要花费O(log(N)).同时,增加的这些索引意味着事务管理器将有更多的工作量(晚一些时候我们会讲到事务管理
想了解更详细的内容, 你可以看这个维基:https://en.wikipedia.org/wiki/B%2B_tree 如果你想知道在数据库中实现B+树的示例，MySQL的核心开发人员的两篇文章: http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/ http://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/ 这两篇文章都着眼于INNODB是怎么处理索引的.
NOTE:*一位读者告诉我,为了底层优化,这个B+树需要完全平衡.
3.4 哈希表(Hash table)
我们的最后一个数据结构是哈希表.想快速找到一个值它这非常有用.而且了解了哈希表将会帮我们搞懂得一个常用的数据库操作:hash join. 这个数据结构也被用于数据库存储一些内部信息(比如说*表锁*或缓冲池,回头我们将介绍到)
哈希表是一种通过它的键快速找到需要元素的一个数据结构.建一个哈希表,你需要申明: - 元素中的一个key - 为这个Key找到一个哈希函数.计划出来的key哈希将给出这个元素的存储位置(桶) - 一个比较这些key的对比函数.一旦找到了正确的树,需要这个函数在桶中找到正确的元素
一个简单的例子,让我们举个可视化的例子:
这个哈希表有10个桶.只里我偷懒只花了5个,但我知道你足够聪明,所以我让你们脑补了剩下的5个. 哈希函数这里我用KEY对10取模.换句话说,我只用了元素的KEY的最后一个数字来林海雪找到它的桶: - 如果最后一个数字是0 ,这个元素存储在0号桶的最后一位 - 如果最后一个数字是1 ,这个元素存储在1号桶的最后一位 - 如果最后一个数字是2 ,这个元素存储在2号桶的最后一位 … 对比函数 这里我用了一个简单的2个整理数的比较.
让我们假定需要一个78的元素 - 哈希表计算78的哈希值为8: - 它在8号桶里开始找,第一个元素就是78. - 它返回元素78 - 它只花费了2次操作(一次计算哈希值,一次在桶里找到这个元素)
好,我们再试找59这个元素: - 哈希表计算59的哈希值为9: - 它在9号桶里开始找,第一个元素就是99.因为99!=59,99不是正确的值 - 相同的逻辑,它找下一个元素(9,79….29) - 元素不存在 - 这次搜索花费了7次操作.
一个好的哈希函数
如你所见到的,你找的值不同,花费竟然不同! 如果现在我们用这个key对100万来取模(它花费6个数字位),每二个搜索只花了一个操作,因为这里没有000059这个桶.真正的挑战是找到一个好的哈希函数,它创建的每个桶都只存少量的元素.
在我这个例子,找到一个哈希函数非常简单.但这只是个简单的例子,找到一个好的哈希函数是很困难的,如果这个是: - 一个字符串(比如一个人名) - 2个字符串(比如一个人的姓和名) - …
**拥有一个好的哈希函数,搜索哈希表的花费是O(1).
数组VS哈希表
为什么不用数组?
恩,你问了一个好问题
- 一个哈希表可以被半加载到内存,剩下的桶可以继续放在磁盘上
- 一个数组必须使用内存中的一块连续空间,如果我们加载大表,很难找到足够的连续空间
- 对于一个哈希表,你可以选择你想的Key(比如这个国家和这个人的名字)
想了解更多哈希表的信息,你可以读这篇文章:讲述的是一种非常有效率的哈希表实现:JAVA HashMap http://coding-geek.com/how-does-a-hashmap-work-in-java/ 不需要你了解JAVA就可以理解文章中的概念
本节完成，下一章节我们将回顾一下内容,并讨论：客户端管理
本篇文章完整分为7节，当前第4节。以下完整章节：