最近在写数据库，很多小伙伴留言询问MySQL索引的底层实现。今天就简单说说吧，少说“怎么回事”，多说“为什么要这样设计”。问题1、数据库为什么要设计索引？图书馆藏书1000万册，要从中找到《架构师之路》。类，二楼文学，三楼IT……IT，还有软件，硬件……软件，并按书名排序……让你快速找到一本书。打个比方，数据库存储了1000万条数据，要从中找出name=”shenjian”的记录，什么时候去一条一条的查找？因此，必须有一个索引来提高数据库的查找速度。问题2.哈希（hash）比树（tree）快。为什么要把索引结构设计成树形呢？加快查找速度的常见数据结构有两种：Hash，如HashMap，查询/插入/修改/删除的平均时间复杂度为O(1)；对于树，比如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度是O(lg(n))；可见无论是读请求还是写请求，hash型索引都比树型索引快，那么为什么要将索引结构设计成树型呢？画外音：80%的同学答不上来。索引设计成树形，这与SQL的要求有关。对于这种单行查询的SQL需求：select*fromtwherename="shenjian"确实是hash索引更快，因为每次只查询一条记录。画外音：因此，如果业务需求是单行访问，比如护照，确实可以使用哈希索引。但是，对于排序查询的SQL需求：分组：groupby排序：orderbyComparison：<,>...对于hash类型的索引，时间复杂度会退化为O(n)，而“有序”的特性树型依然可以保持O(log(n))的高效率。任何偏离要求的设计都是耍流氓。还有一件事，InnoDB不支持哈希索引。问题3、数据库索引为什么要用B+树？为了保持知识体系的完整性，简单介绍以下几种树。1、第一种：二叉查找树二叉查找树，如上图所示，是最为人熟知的数据结构，就不做介绍了。为什么不适合做数据库索引呢？当数据量大的时候，有时候树的高度会比较高，数据量大的时候，查询会比较慢；每个节点只存储一条记录，可能导致一次查询多次磁盘IO；画外音：这棵树经常出现在大学教科书里，所以最为人熟知。2、第二种：B-treeB-tree，如上图所示，其特点是：不再是二分查找，而是m-fork查找；叶节点，非叶节点，存储数据；中序遍历，可以得到所有的Node；画外音，我真的不想介绍这个特性：非根节点j包含的关键字个数满足，(┌m/2┐)-1<=j<=m-1，这个条件必须是结点分裂时相遇。B树作为实现索引的数据结构而被创建，因为它可以最好地利用“局部性原理”。(1)什么是局部性原则？局部性原理的逻辑是这样的：内存读写块，磁盘读写慢，而且慢得多；磁盘预读：磁盘读写不是按需读取，而是按页预读，一次读取一页数据，每次加载更多的数据，如果以后要读取的数据在这一页，可以避免以后的磁盘IO，提高效率；（画外音：通常情况下，一页数据是4K。）局部性原则：软件设计要尽量遵循“数据读取集中”和“当一个数据被使用时，附近的数据大概率会被读取”。beused”，这样磁盘预读可以充分提高磁盘IO；(2)B树为什么适合做索引？由于是m分叉，高度可以大大降低；每个节点可以存储j条记录。如果节点大小设置为页面大小，比如4K，可以充分利用预读特性，极大地减少磁盘IO；第三种：B+树B+树，如上图，仍然是m-fork搜索树。在B树的基础上做了一些改进：非叶子节点不再存储数据，数据只存储在同一层（画外音：B+树中根到每个节点的路径长度相同，但是B树不是这样的。）叶子之间，增加一个链表获取所有节点，不再需要中序遍历；这些改进使得B+Trees比B-trees有更好的特性：范围搜索，定位到min和max后，中间的叶子节点就是结果集，没有顺序回溯；（画外音：范围查询在SQL中用的比较多，这就是B+树与B树的优势对比***。)叶子节点存储实际的记录行，比较紧凑，适合大量数据的磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；非叶子节点不存储实际记录，如果只存储记录的KEY，那么在内存相同的情况下，B+树可以存储更多的索引；***，从数量上讲，为什么m-forkB+树的高度比二叉查找树低很多？粗略计算一下来看看：(1)局部性原则，设置一个节点的大小为一页，每页4K，假设一个KEY有8个字节，一个节点可以存放500个KEY，即j=500(2)m叉树，大概m/2<=j<=m，也就是差不多可以有1000棵叉树。那么：一层树：1个节点，1*500个KEY，size4K二层树：1000个节点，1000*500=50WKEY，size1000*4K=4M三层树：1000*1000个节点，1000*1000*500=5亿个KEY，大小1000*1000*4K=4G画外音：嗯，大家帮我看看有没有算错。可以看出，存储大量数据（5亿）不需要很高的树深（高度3），索引也不会占用太多内存（4G）。总结（1）数据库索引用于加快查询速度（2）虽然哈希索引是O(1)，树索引是O(log(n))，但是SQL有很多“有序”的要求，所以数据库使用树索引（3）InnoDB不支持hash索引（4）数据预读的思路是：磁盘读写不是按需读，而是按页预读，一次会读一页数据,并且每次会加载更多数据数据，以减少以后的磁盘IO(5)局部性原则：软件设计尽量遵循“数据读取集中”和“当一个数据被使用时，靠近它的数据将被使用”大概率使用”，这样磁盘预读可以充分提高磁盘IO(6)数据库的索引是最常用的B+树：非常适合磁盘存储，可以充分利用的原理本地化、磁盘预读；树高极低，可存储大量数据；索引本身占用的内存很少；可以很好的支持单点查询、范围查询、有序查询；【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此查看该作者更多好文
