如果再有人问你数据库的原理，把这篇文章给他( 五 ) _数据库

如果元素最后一位是 0，则进入哈希桶0，
如果元素最后一位是 1，则进入哈希桶1，
如果元素最后一位是 2，则进入哈希桶2，
…我用的比较函数只是判断两个整数是否相等。

【译者注：取模运算】
比方说你要找元素 78：

哈希表计算 78 的哈希码，等于 8 。
查找哈希桶 8，找到的第一个元素是 78 。
返回元素 78 。
查询仅耗费了 2 次运算（1次计算哈希值，另一次在哈希桶中查找元素）。

现在，比方说你要找元素 59：

哈希表计算 59 的哈希码，等于9 。
查找哈希桶 9，第一个找到的元素是 99 。因为 99 不等于 59，那么 99 不是正确的元素。
用同样的逻辑，查找第二个元素(9)，第三个(79)，……，最后一个(29) 。
元素不存在。
搜索耗费了 7 次运算。

一个好的哈希函数
你可以看到，根据你查找的值，成本并不相同。
如果我把哈希函数改为关键字对 1,000,000 取模（就是说取后6位数字），第二次搜索只消耗一次运算，因为哈希桶 00059 里面没有元素。真正的挑战是找到好的哈希函数，让哈希桶里包含非常少的元素。
在我的例子里，找到一个好的哈希函数很容易，但这是个简单的例子。当关键字是下列形式时，好的哈希函数就更难找了：

1 个字符串（比如一个人的姓）
2 个字符串（比如一个人的姓和名）
2 个字符串和一个日期（比如一个人的姓、名和出生年月日）
…

如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1) 。
阵列 vs 哈希表
为什么不用阵列呢？
嗯，你问得好。

一个哈希表可以只装载一半到内存，剩下的哈希桶可以留在硬盘上。
用阵列的话，你需要一个连续内存空间。如果你加载一个大表，很难分配足够的连续内存空间。
用哈希表的话，你可以选择你要的关键字（比如，一个人的国家和姓氏）。

全局概览我们已经了解了数据库内部的基本组件，现在我们需要回来看看数据库的全貌了。
数据库是一个易于访问和修改的信息集合。不过简单的一堆文件也能达到这个效果。事实上，像SQLite这样最简单的数据库也只是一堆文件而已，但SQLite是精心设计的一堆文件，因为它允许你：

使用事务来确保数据的安全和一致性
快速处理百万条以上的数据

数据库一般可以用如下图形来理解：

文章插图

撰写这部分之前，我读过很多书/论文，它们都以自己的方式描述数据库。所以，我不会特别关注如何组织数据库或者如何命名各种进程，因为我选择了自己的方式来描述这些概念以适应本文。区别就是不同的组件，总体思路为：数据库是由多种互相交互的组件构成的。
核心组件：

进程管理器（process manager）：很多数据库具备一个需要妥善管理的进程/线程池。再者，为了实现纳秒级操作，一些现代数据库使用自己的线程而不是操作系统线程。
网络管理器（network manager）：网路I/O是个大问题，尤其是对于分布式数据库。所以一些数据库具备自己的网络管理器。
文件系统管理器（File system manager）：磁盘I/O是数据库的首要瓶颈。具备一个文件系统管理器来完美地处理OS文件系统甚至取代OS文件系统，是非常重要的。
内存管理器（memory manager）：为了避免磁盘I/O带来的性能损失，需要大量的内存。但是如果你要处理大容量内存你需要高效的内存管理器，尤其是你有很多查询同时使用内存的时候。
安全管理器（Security Manager）：用于对用户的验证和授权。
客户端管理器（Client manager）：用于管理客户端连接。
……

工具：