数据库中的几种数据结构
阵列
- 二维阵列是最简单的数据结构。一个表可以看做是一个阵列：
| |column 0|column 1|column 2|
|--|--|--|--|--|
|row 0|fy|4|CHN|
|row 1|ame|1|CHN|
|row 2|maybe|2|CHN|
|row 3|charles|3|CHN|
|row 4|xNova|5|CHN|
|...|..|...|..|
|row n|..|..|..|..
这个二维阵列是带有行与列的表：
- 每个行代表一个主体
- 列用来描述主体的特征
- 每个列保存某一种类型对数据
当要查找特定的值时，这种数据结构需要对每一行的值进行判断。这会造成N次运算，复杂度是O(N)
树和数据库索引
- 二叉查找树/二叉搜索树：
一种带有特殊属性的二叉树，每个节点的值满足：- 比保存在左子树的任何键值都要大
-
比保存在右子树的任何键值都要小
image
这个树有N=15个元素。如果要找208，会从根节点开始寻找：
- 136 < 208 --> 去找节点136的右子树
- 298 > 208 --> 去找节点398的左子树
- 50>208 --> 去找节点250的左子树
- 200<208 --> 去找节点200的右子树。但是 200 没有右子树，值不存在（因为如果存在，它会在 200 的右子树）
一次查询的成本基本就是树内部的层数，这个成本是log(N)
B+树索引
查找一个特定的值时，二叉查找树挺好用的，但是当我们需要查找某一个范围之间的多个元素时，我们还是要对每一个节点进行遍历，以判断它是否处于那两个值之间,这样你必须读取整个树，成本是O(N)。
为了解决这个问题，现代数据库使用了一种修订版的树---B+树:
- 只有最底层的叶子节点才保存信息
-
其它节点只是用来指引到正确的节点
image
可以看到节点多了两倍，同时最底层的节点是跟后续节点相连的。
用这个B+树，如果要找某个范围内(例如40到100之间)的值：
- 找到40（49不存在则找40之后最贴近的值），就像在二叉查找树中的那样。
- 向后遍历节点，直到找到100
找到了 M 个后续节点，树总共有 N 个节点。对指定节点的搜索成本是 log(N)，跟上一个树相同。但是当你找到这个节点之后，你可以通过后续节点的连接得到 M 个后续节点，这需要 M 次运算。那么这次搜索只消耗了 M+log(N) 次运算
这种方式方便查找，但是需要在节点之间保持顺序，所以在插入和删除数据时，为了维护这个B+树，需要以每个索引O(log(N))的代价来更新索引。这样的话就会减慢插入/更新/删除的操作。
哈希表
这个数据结构被数据库用来保存一些内部的东西（比如锁表或者缓冲池）
哈希表可以通过关键字来快速找到一个元素，为了构建一个hash表，你需要定义：
- 元素的关键字
- 哈希函数： 根据元素的关键字给出对应的hash值
- 比较函数：通过hash值在桶中找到需要的元素
例子：
对于这个存储数字的hash表，我们定义：
- 元素关键字： 数字本身
- 哈希函数： 对10取模
def hash(num): return num % 10 - 比价函数：判断两个整数是否相等
寻找元素78：
- hash(78) = 8
- 查找hash桶8，找到第一个元素78,
- 返回78
搜索耗费了2次运算
找元素 59：
哈希表计算 59 的哈希码，等于9。
查找哈希桶 9，第一个找到的元素是 99。因为 99 不等于 59， 那么 99 不是正确的元素。
用同样的逻辑，查找第二个元素(9)，第三个(79)，……，最后一个(29)。
元素不存在。
搜索耗费了 7 次运算。
从列子可以看出，根据查找的值，每次寻找的成本(计算次数)可能并不相同。
一个好的hash函数会将所有的元素尽可能地均匀分配在hash桶中，这样会尽可能地减少查找次数。
如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。
阵列 vs 哈希表
- 一个哈希表可以只装载一半到内存，剩下的哈希桶可以留在硬盘上。
- 用阵列的话，你需要一个连续内存空间。如果你加载一个大表，很难分配足够的连续内存空间。
- 用哈希表的话，你可以选择你要的关键字（比如，一个人的国家和姓氏）。
