相信很多程序员朋友对数据的索引并不陌生，最常见的索引是 B+ Tree 索引，索引可以加快数据库的检索速度，但是会降低新增、修改、删除操作的速度，一些错误的写法会导致索引失效等等。

但是如果被问到，为什么用了索引之后，查询就会变快？B+ Tree 索引的原理是什么？这时候很多人可能就不知道了，今天我就以 MySQL 的 InnoDB 引擎为例，讲一讲 B+ Tree 索引的原理。

索引的基础知识

MySQL 的基本存储结构是页，大概就是这个样子的：

索引是存储引擎用于快速查找记录的数据结构，MySQL 数据库内部索引是由不同的引擎实现的，主要说一下最常用的InnoDB引擎中的索引，InnoDB引擎中的索引是使用B+ 树的结构来存储的，B+ 树结构如下图：

先来说一下B+ 树的特点：

• 叶子节点（最下面一层）存储关键字（索引字段的值）信息及对应的全部数据记录。

• 非叶子节点只存储关键字的信息及子节点的指针。

这个问题和线性查询、二分查询是有很大关系的。索引后的数据可以使用二分法查询，未索引的数据查询需要线性查询。下面详细说一下这两者之间的性能区别。

1、两者的查询原理

①、线性查询

线性查询又称顺序查询，它的查询原理就是从第一条记录开始，逐个比较要查找的字段，直到字段内容和查找值相等，则查找成功，返回结果。若比较结果与字段所有记录都不等，则查找失败。下面举例说明：

需要在某个记录数为N的数组a[]中查找元素k，那么，线性查询就是从a[1]开始和k进行对比，对比相等则返回a[i]，如果，不相等则继续下一个查询， i=i+1。直到 i=N为止。那线性查询的性能就一目了然：

想想汉语字典的拼音和部首索引就可以了，就是这么简单。

很高兴能够看到和这个问题！

什么是数据库索引？

数据库中的索引类似于书籍中的目录，目录可以快速获取信息，而不需要阅读整本书。

在数据库中，索引可以让数据库程序在不扫描整张表的情况下找到所需的数据。本书包含一组章节，并列出包含章节的页码。数据库中的索引是表中一列或多列中的一组值，相应的索引列表代表这些值。

索引字段可以是单个字段也可以是多个字段的组合，如果是多个字段的组合，其索引值的排列首先按第一个字段值进行排列，如果其值相同，再按第二个字段的值进行排列，以此类推。

使用索引的意义有哪些？

数据库中的糖指数类似于书中的目录值，用于提高信息检索速度。

数据库索引可以理解成图书馆的书架，书架按书目分类，或者理解成一本书的目录。想想如果没有这些目录，要找一本书中内容，就要从头把书翻一遍，或者把图书馆的书都找一遍，这样会有多慢？

数据库建立索引也是这个原理，数据有了分类目录了，查询数据的时候，先查找目录就会快了很多。

不过对现在的海量数据来讲，有了索引还是杯水车薪，查询依然很慢，而且建立索引要占用额外的存储空间，对数据库来讲存贮空间是非常值钱的，商业数据库存贮空间收费昂贵。

真正的海量数据存贮，查询效率都是用计算机硬件堆起来的，就是用钱堆起来的，不要想在软件上做点优化就会有多少本质的提高。

具体硬件优化有很多手段，前端查询，数据库缓存，分布式应用等等，要想掌握好数据库的优化，去看看实际的商业应用案例最好，书本上的那些东西，没多大意义。

以查字典为例，来说明这个问题。

先想象一下有一本字典，里面的字是随意排列的，我们要查一个字，就只能一页一页翻过去查找，这样下来查一个字就会花很多时间，如果运气不好，我们要找的字在最后一页，就得翻几千页了。用数据库的术语叫遍历（full scan）。

为了缩短查询时间，我们把字典里的字按照拼音字母的顺序排列好。这样查字的时候，查看一下中间那一页，就可以知道我们要查的字是在前面还是在后面。比如在前面，我们就查看1/4处的那一页，如此反复直到我们找到要查的字为止。那么这么做我们得查多少次呢？一本六万多页的字典最多查16次就能找到您想要的那一页了。这种方法要比遍历的方法快得多。用数据库的术语叫B-TREE(二叉树)。

如果我们不知道发音想按部首查字典又该怎么办呢？字典里按照部首的顺序做了个表，查这个表就可以快速查到解释那个字的页码了。这个表用数据库的术语就叫索引。

数据库里的数据经常会有千万条以上，双十一某宝的数据，一分钟的交易数据大概就能突破千万。这么大量的数据一条一条遍历恐怕是不现实的，在这样的数据库里，建立完善的索引是必须的。有了索引以亿为单位的数据，也只要做几十次检索就足够了。

索引简单来说就是一本字典的目录，数据量小的时候，字典比较薄，全部一扫而过，瞬间就能查询到你指定的数据，但是随着数据量的增加，字典越来越厚，全部扫，费时费力（消耗大量的系统内存，磁盘瞬间IO也会越来越吃紧，占用大量系统资源，进程得不到释放），这时候如果给字典新增加个对应章节（表）目录，我们直接通过目录就能快速检索到有用数据，不会漫无边际的全部扫，再去过滤。当然由于你新建了目录（索引），肯定会占用一定的字典空间，当然针对你的查询来说，通过空间换时间，这个还是很值得的。针对插入，由于你需要往指定目录（有索引的表）插入数据，字典（数据库系统）需要重新更新制定目录并且维护目录信息，因此插入这个过程会慢，如何解决这一问题呢，我们可以删除指定目录（索引或者分区），数据全部处理好以后重新创建目录。

插入的时候对索引字段计算哈希值，把哈希值和行号对应关系放进一张哈希表。

查询的时候对索引字段计算哈希值，从哈希表中查到行号，就能找到这一行了。

用redis的key hash list能模拟一个简单的带索引的关系型数据库。

建索引就是 把 数据表 的一个 字段 作为 key,建立查找的表，