数据库索引，到底是什么做的？

近期写数据库，不少朋友留言问MySQL索引底层的实现，今天简单聊一聊，少讲“是怎么样”，更多说说“为什么设计成这样”。

问题1. 数据库为什么要设计索引？

图书馆存了1000W本图书，要从中找到《架构师之路》，一本本查，要查到什么时候去？

于是，图书管理员设计了一套规则：

(1)一楼放历史类，二楼放文学类，三楼放IT类…

(2)IT类，又分软件类，硬件类…

(3)软件类，又按照书名音序排序…

以便快速找到一本书。

与之类比，数据库存储了1000W条数据，要从中找到name=”shenjian”的记录，一条条查，要查到什么时候去？

于是，要有索引，用于提升数据库的查找速度。

**
问题2. 哈希(hash)比树(tree)更快，索引结构为什么要设计成树型？**

加速查找速度的数据结构，常见的有两类：

(1)哈希，例如HashMap，查询/插入/修改/删除的平