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