数据库核心：索引，你知道多少？
【这是一猿小讲的第 80 篇原创分享】
今天聊点面试中经常聊的话题 —— 索引！虽然网上已经有很多类似的文章啦，但是我们开启的方式却不同。
01. 体验很重要
首先打造一个世界上最简单的迷你版数据库，一起来围观体验。
#!/bin/bash
# 迷你版数据库对外提供的函数
method=$1
# 向迷你版数据库中存放的key
key=$2
# 向迷你版数据库中存储的value
value=$3
# key-value 数据存储
function db_set() {
echo "$key,$value" >> database
}
# 根据 key 查询数据库存储的 value
function db_get() {
grep "^$key," database | sed -e "s/^$key,//" | tail -n 1
}
case $method in
(db_set)
db_set
;;
(db_get)
db_get
;;
(*)
echo "Error method"
;;
esac这款迷你版的数据库，实现了一个 key-value 的简易数据存储，主要由数据存储（db_set）、查询（db_get）两个函数构成。
当我们调用 db_set key value，它将在数据库中保存你所输入的 key 和 value。
其中 key 和 value 几乎可以是任何内容，例如，值可以是一个 JSON 文档。然后，当我们调用 db_get key，它会查找与输入 key 相关联的最新值并返回。
例如，向迷你数据库插入数据。
./minidb.sh db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}' ./minidb.sh db_set 42 '{"name":"San Francisco","attractions":["Godlen Gate Bridge"]}'
然后，从迷你数据库查询指定的数据。
./minidb.sh db_get 42
./minidb.sh db_get 123456
迷你数据库到这就算体验完了，原理超级简单，就是往 database 文件尾部追加数据就好了，其实许多数据库内部实现都和 db_set 类似，它们都使用日志文件，因为它只支持追加式的方式更新。
但是，大家有没有想过？
如果日志文件保存了大量的记录，那么数据库的查询（db_get）肯定会非常差。每次要查找一个 key 对应的值，就必须扫描整个数据库文件来查找 key 出现的位置，这样开销会很大，有没有高效的解决方案呢？
为了高效地查找数据库中特定的 key 的值，那么就需要引入新的数据结构 —— 索引！
02. 索引
哈希索引。
我们继续以 key-value 数据的索引为基础，假设数据存储全部采用追加式的文件组成，像上面的迷你数据库那样，数据都追加到 database 文件中。那么最简单的索引策略，莫过于把每个 key 对应文件中的字节偏移量（也就是在文件中的位置），保存到内存中的哈希表中（Hashtable 或 HashMap），这样就可以快速找到每个值的位置。
每当向数据库追加新的 key-value 时，也就需要更新内存中的 HashMap 来记录刚刚写入数据的偏移量；当查找某个值时，使用 HashMap 来找到文件中的存储位置，然后读取其内容。
上面的方式虽然很简单，但是的确是一个可行的方法。静下来思考，多数实现其实都是换汤不换药，变化无非也就是通过计算 key 的 hash 值，然后映射对应的 value。
但是哈希索引使用起来，存在一定的问题（注意，这块面试的时候经常会聊呦！）。
- 哈希表必须全部放入内存，如果有大量的 key 的情况下，表现就不会那么好啦；
- 区间查询效率不太好，例如要查询 key0000 和 key9999 区间的所有键，只能采用逐个查找的方式查询每一个键；
- 由于哈希索引数据没有按照索引值顺序存储，所以无法用来进行排序。
- 。。。。。。
面对哈希索引的一些限制，在 LSM-Tree、B-Tree 等索引结构上得到了很大的解决，时间关系，今天就不深入展开啦。
03. 常见面试题
- B-Tree 与 哈希索引的比较？ 参见官方答案： https://dev.mysql.com/doc/refman/8.0/en/index-btree-hash.html
- 索引能提升查询效率，是不是越多越好呢？ 索引是额外的数据结构，但是维护这个额外的数据结构肯定也会引入开销，特别是在新数据写入的时候。由于每次写数据时，需要更新索引，所以索引也会降低写的速度，设计系统的时候一定要进行权衡。
- 聊聊哈希表、二叉搜索树、B-Tree、B+Tree 常见数据结构？学习算法的好网址，建议收藏。 https://www.cs.usfca.edu/~galles/visualization/OpenHash.html https://www.cs.usfca.edu/~galles/visualization/BST.html https://www.cs.usfca.edu/~galles/visualization/BTree.html https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
文中有些观点来自于近期看的一本书《数据密集型应用系统设计》，开卷有益，希望大家抽时间多读书、多看报、少吃零食多睡觉。最后，希望通过本次简短的分享，都有所启发。