SQL注入（ SQL injection ）是一种将恶意代码插入到程序 SQL 语句中，从而误导数据库执行恶意逻辑的攻击技术。通过 SQL 注入，攻击者可以达到获取敏感信息，窃取访问权限等目的。

因此，在设计数据库应用时，必须警惕 SQL 注入风险，并加以防范。

任何系统通常都有用户，数据库因而少不了用户表，少不了要保存用户密码。那么，密码能明文保存吗？肯定不能！ 如果用户密码用明文保存，一旦数据库被拖库，用户密码就全泄露了呀！用户密码泄露可不是件小事，影响的也不仅仅是泄露站点，因为用户通常用同一个密码走天下！ 写到这不禁想起多年前发生的 CSDN 拖库事件，泄露了大量用户的密码，笔者的账号密码也在其中。顺便吐槽一下，CSDN 烂不是一天两天了，一个程序员交流网站竟然明文保存密码！ 当年我还年轻，好多网站的账号密码都是一样的。黑客拖库得到我的账号密码后，可以用它来登录我的 QQ ，我的邮箱，甚至是网银！想想就觉得可怕！ 从此以后，我养成了一个习惯——每个网站都用随机生成的独立的密码。为此，我还自己写了个密码管理器，支持随机生成密码、加密保存密码、按域名等关键字搜索密码。不过，后来懒得自己折腾，直接入了 1Password 。 话说回来，您可能会觉得：只要数据库保护得足够好，不被拖库，明文保存密码似乎也问题不大。其实拖库是无法百分之百避免的，因为系统总有漏洞，比如 SQL注入 漏洞就可以用来拖库。 因此，拖库肯定要防，如何将拖库损失降到最低也必须考虑。况且就算没有拖库，明文保存的密码也有由内部渠道泄露的风险。那么，密码如何加密保存呢？ 哈希 您可能会想到，先选择一个加密密钥，然后对密码进行加密后再保存到数据库；查询时再用密钥对密码进行解密。这看上去是个不错的方案，但事实并非如此，原因有二： 如果数据和密钥同时被泄露，密码就可以被解密出来； 密码仍可能由内部渠道泄露，因为系统管理员可能同时拥有加密密钥和数据库权限； 因此，最理想的做法是：让密码保存后，无法再被复原出来。换句话讲，加密必须是 不可逆 的。这时，您应该会想到 md5 、sha128、 sha256 等哈希算法。是的，用户密码通常都是用哈希算法加密后再保存到数据库的。 保存 用户注册或修改密码时，系统用哈希算法将用户的明文密码转换成一个 哈希值 ，再保存到数据库。以密码 123456 为例，用 md5 将其转换成一个哈希值： 1 2 3 >>> import hashlib >>> hashlib.md5(b'123456').hexdigest() 'e10adc3949ba59abbe56e057f20f883e' 哈希值作为密码的替代品，保存到数据库。这样一来，就算数据库被拖，黑客也无法根据哈希值还原出密码来。 验证 数据库不保存密码，那登录时如何验证用户的密码是否正确呢？ 哈希算法有一个特点，相同的输入产生的输出一定也是相同的。换句话讲，同一个密码算出来的哈希值一定是一样的；不同密码算出来的哈希值通常是不一样的。 由于哈希冲突的存在，两个不同的密码算出来的哈希值也有可能是一样的。但只要哈希值空间足够大，哈希冲突的概率就可以降到极低。以 md5 算法为例，哈希冲突的概率几乎为零。因此，可以认为不同密码算出来的 md5 值是不一样的。 利用这个特性，登录验证时可以用同样的哈希算法将用户提供的密码转换成一个哈希值，再跟数据库中的进行比较。如果两个哈希值相同，说明用户提供的登录密码正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 # 数据库中的哈希值（原密码是：123456） >>> hash_in_db = 'e10adc3949ba59abbe56e057f20f883e' # 用户输入的密码 >>> password_input = b'123456' # 对密码求哈希再跟数据库中的比较，相等表示密码正确！ >>> hashlib.

前面我们介绍了 哈希索引 和 LSM树索引 ，它们都基于日志结构式的数据文件。虽然工程界对这种索引的认可度正与日俱增，但还远不是最受欢迎的索引技术。

那么，目前应用最广的索引技术又是什么呢？

您可能早就有所耳闻——这就是本文要探讨的 B树（ b-tree ）索引。B树可以说是数据库索引技术中的武林盟主，能够几十年长盛不衰，必定有它自己的独门秘诀。

索引结构

跟我们在 LSM树 一节中提到的 SSTable 一样，B树也是将数据组织成有序形式，因此支持范围查询。尽管如此，它们的底层结构却完全不同，B树有自己独特的设计哲学。

上次我们分享了采用哈希索引实现的存储引擎，它总是将写操作不断追加到数据文件，就跟写日志一样。这种日志结构式的存储引擎，数据记录顺序由写入时间决定，同一键的旧记录由新记录取代。

SSTable

由于数据在写入时，自动切分成一个个文件。数据库需要在后台对文件进行合并，以减少文件数，进而加快查询。如果待合并文件里的数据是有序的，我们就可以采用归并排序算法来提高合并效率。

虽然这看起来会违背顺序写的原则，但也有办法解决，我们稍后介绍。

现在，我们将数据文件格式改成这样：①文件中的所有记录，按照 键（ key ）来排序；②排序保证了每个键只在文件中出现一次，不会有重复的旧记录。姑且将这种格式叫做 排序字符串表（ sorted string table ）简称 SSTable 。

我们介绍过一个用几行 Shell 代码实现的简陋数据库，它的插入性能很好，但查询性能很差。

我们都知道，想要提升数据库的查询速度，索引必不可少 。那么，索引的底层结构都是怎样的呢？它们又是如何工作的呢？

实际上，数据库索引技术因底层数据结构不同，可以分为好几种：

• 哈希索引（ hash index ）
• LSM树（ log structured merge tree ）
• B树（ b-tree ）

其中，哈希索引的结构最为简单，但也很常用。今天我们就先将它一举拿下！

哈希索引结构

键值对存储引擎其实跟编程语言中的 字典 （ dictionary ）类型很像，而字典底层通常是用 哈希表（ hash table ）实现的。既然哈希表可以用来索引内存中的数据，应该也可以用来索引磁盘数据吧？

最近重读《数据密集型应用系统设计》这本书，看到第三章《数据存储与检索》，主要讲数据库内部的索引技术。

从本质上讲，数据库主要是做两件事情：

1. 当你给它数据时，它帮你保存数据（存储）；
2. 当你查询数据时，它帮你取回数据（检索）；

这两件事情看似简单，背后却暗含玄机。那么，数据库内部到底是如何存储数据的呢？又是如何检索数据的呢？

你可能会有这样的疑问：我作为一个开发人员，为什么需要知道数据库内部是怎么工作的呢？