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

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

索引的基础知识

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

在这里，我们需要了解以下几点（非常重要）：

• 当我们用 MySQL 的 InnoDB 引擎创建表，有且只能有一个主键；如果我们没有显示地指定之间，那么MySQL 会自动生成一个隐含字段作为主键；

• 聚集索引：以主键创建的索引；聚集索引的叶子节点存储的是表中的数据；

• 非聚集索引：非主键创建的索引；非聚集索引在叶子节点存储的是主键和索引列；使用非聚集索引查询数据，会查询到叶子上的主键，再根据主键查到数据（这个过程叫做回表）。

页和页之间、页和数据之间的关系

我们以聚集索引做讲解，页和页之间、以及页和数据之间的关系是这样的：

• 数据页和数据页之间，组成一个双向链表；

• 每个数据页中的记录，是一个单向链表；

• 每个数据页都根据内部的记录生成一个页目录（Page directory），如果是主键的话，可以在页目录中使用二分法快速定位；

• 如果我们根据一个非主键、非索引列进行查询，那么需要遍历双向链表，找到所在的页；再遍历页内的单向链表；如果表内数据很大的话，这样的查询就会很慢。

B+ Tree 索引的原理

先让我们看看 B+ Tree 索引大概是什么样子（以聚集/主键索引为例）：

• 假如这时候我们要查询 id = 16 的数据：

• 查询页-1，找到页-2 存储的是小于 30 的数据；

• 查询页-2，找到页-5 存储的是 10~20 的数据；

• 查询页-5，找到 id = 16 的数据。

很显然，没有用索引的时候，需要遍历双向链表来定位对应的页，而有了索引，则可以通过一层层“目录”定位到对应的页上。

为什么 B+ Tree 索引会降低新增、修改、删除的速度

• B+ Tree 是一颗平衡树，如果对这颗树新增、修改、删除的话，会破坏它的原有结构；

• 我们在做数据新增、修改、删除的时候，需要花额外的时间去维护索引；

• 正因为这些额外的开销，导致索引会降低新增、修改、删除的速度。

思考题，欢迎留言讨论

现在你是否理解了 B+ Tree 索引的原理？

最后再留一个思考题：为什么官方建议使用自增长主键作为索引？大家可以在留言中写下你的答案。

我将持续分享Java开发、架构设计、程序员职业发展等方面的见解，希望能得到你的关注；关注我后，可私信发送数字【1】，获取海量学习资料。

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

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

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

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

• 每个叶子节点相当于MySQL中的一个数据页，同层级的叶子节点以双向链表的形式连接。

• 每个节点中存储了多条记录，记录之间用单链表的形式连接组成了一条有序的链表。

• 在 B+ 树中检索数据时：每次检索都从根节点开始，一直搜索到叶子节点。

InnoDB 的数据是按数据页为单位来读写的。也就是说，当需要读取一条记录的时候，并不是将这个记录本身从磁盘读取出来，而是以页为单位，将整个也加载到内存中，一个页中可能有很多记录，然后在内存中对页通过二分法进行检索。在InnoDB 中，每个页的大小默认是16kb。

总体来说，MySQL中的索引用到了B+树、链表、二分法，实现了快速查找数据。

MySQL索引类型

InnoDB 中有两种索引类型：主键索引与辅助索引。

• 主键索引（聚集索引）：每个表只有一个主键索引，叶子节点同时保存了主键的值以及对应的全部记录。

• 辅助索引（非聚集索引）：叶子节点保存了索引字段的值以及主键的值。

我们以上图中Person表 为例，其中id 是主键，name 是辅助索引，接下里我们来看一下InnoDB引擎中数据检索过程：

• 若需要查询 id=1 的数据，只需要使用主键索引中检索就可以查询到数据。（红色线）
  

• 若需要搜索 name='Jacy' 的数据，需要使用非聚集索引与聚集索引，需要2步（蓝色线）：
  

1. 先通过辅助索引中检索 name='Jacy'的数据，获取 id 的值。

2. 再通过id值 到主键索引中 检索id=12的数据。

接下来，我们再看下以下查询的数据检索过程。

主键索引（或唯一索引）查询

上图中所有的数据都是唯一的，我们查询26的记录，过程如下：

• 首先把page1 页加载到内存中通过二分法查找。

• 确定26位于[20,40)中间，然后加载20所关联的page3 页.

• 将page3 页加载到内存中，采用二分法找到26的记录后退出。

非唯一索引查询

上图中查询26的所有记录，数据不唯一，过程如下：

• 将page1 页加载到内存中通过二分法查找。

• 确定26位于[20,40)中间，然后加载20所关联的page3 页。

• 将page3 页加载到内存中通过二分法找到最后一个小于26的记录是23，然后通过链表从23开始向后访问，找到所有的26记录，直到遇到第一个大于26的值退出。

模糊查询

上图中查询以 b字母开头的所有记录，过程如下：

• 将page1页加载到内存中，通过二分法查找最后一个小于等于b的值(b)，和第一个大于b的(z)，b指向叶节点page3，z指向叶节点page5。

• 如此一来，可以确定以 b 开头的记录存在于[page3,page5) 这个范围内。

• 最后依次加载page3 到内存中，通过二分法找到第一条b开头的记录，然后以链表方式继续向后访问page4 中的记录，直至遇到一个字母为z的值退出。

当我们使用 '%b%' 全模糊查询时，通过索引我们还可以快速定位所在的页嘛？

如上图包含b字母的数据在每个页中都存在，因此无法判断包含 b 的记录在哪些页中，只能通过IO的方式加载所有页，遍历所有记录进行过滤，才可以找到包含b的记录。因此使用LIKE %b%进行全模糊查询时，索引是无效的。

更多内容可以浏览《MySQL数据库中如何正确的理解与使用索引》https://www.toutiao.com/i6759910720944472588/

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

1、两者的查询原理

①、线性查询

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

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

• 最好的情况就是对比1次就找到结果。
• 最差的情况就是需要对比N次才能找到结果。
• 平均计算，就是N/2次能找到结果。

②、二分查询

二分法查询也可以说是分段查询。主要原理就是对已经排序的一组数据进行中间分段，中间分界点和查询值对比。如果数值小于分界点，则要查找的数落在前半段；如果数字大于分界点，则要查找的数落在前半段；如果等于分界点，则要查找数就已经找到。下面同样举例说明：

需要在某个记录数为N且已经排好序的数组a[]中查找元素K，那么，二分查询首先是确定数组的中点a[x]，其实也就是a[N/2]这个值（N/2采用进一法取整）。然后对比a[x]和K值，按照前面的方法循环缩小对比的区间，最终找到想要的值。二分查询的性能如下：

• 二分法查询N条记录需要log2（N）次对比就能找到结果。
• 前提是：数组必须要排好序

★从上面两种查询法原理可以看到，当数组N比较大时，二分查询的查询性能明显优于线性查询。当数组N较小时，则线性查询的性能更好，因为它少了求中值的开销。

2、索引给数据库查询带来的性能变化

数据库中建立索引其实就是对数据库表中一列或多列的值进行排序的结构。其实就是为了给二分查询做好排序的前提。结合前面两种查询的原理，我们就很容易理解数据库中索引变快的原因了。其实，数据库通常情况下，数据量都是比较大的，一般都是上万条，甚至达到亿级记录。我们用前面原理中的公式计算对比一下：

• 在10万条记录中查找一个值：那么，N=100000；
• 线性查询性能=N/2，计算可得，平均需要对比50000次;
• 二分查询性能=log2(N)，计算可得，大约需要17次；

从上面计算对比，我们可以看到，索引好了用二分查询的性能会比线性查询快非常多。

3、数据库哪里应该加索引

虽然加了索引后，查询性能提升很多。但是在数据库里面也是不所有字段都加索引的，因为，数据库的整体性能不仅需要考虑查询性能，还需要考虑写入性能。当你在数据库中某个字段加入索引后，该字段就需要建立对应的索引指针。每次新写入或者修改字段的记录，都需要额外写入索引指针。所以，在数据库中，加入索引会加快搜索性能，但也会相应降低一点点写入性能。所以，数据库中建立索引一般在以下几种情况建立索引。

• 经常需要搜索的列，增加索引可以加快搜索速度；
• 作为主键的列，强制该列的唯一性和组织表中数据的排列结构；
• 在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；
• 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的
• 在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间
• 在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度

总结

总之，数据库中因为存在大量的数据，建立索引相当于对数据进行了排序，可以使用二分查询法来查询数据，确实会大大提高查询的速度。但是也会相应降低一点点写入的速度，所以，数据库中的索引也是有针对性的建立索引的。

感谢阅读！我是数智风，用经验回答问题，欢迎评论关注。

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

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

什么是数据库索引？

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

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

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

使用索引的意义有哪些？

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

使用索引搜索数据不需要扫描整个表格，也不需要快速搜索数据。

索引使用的成本

糖指数需要占据物理内存之外的位置。创建和运行索引需要一定的时间。

?更新索引表时，服务数据重建的速度要放慢。

数据库索引类别

索引不需要重新排列文件中记录的顺序。一个文件可以有多个相互关联的索引，每个索引支持键码，通过索引可以快速访问文件中的记录。

1、静态索引

静态索引是在创建文件时创建的索引结构。文件完成后，只有在重新组织时才能修改。2、动态索引

动态索引是在创建文件时创建的索引结构。当执行插入和删除等操作时，索引结构本身会发生变化。

索引的缺点

在添加、修改、删除数据时，需要维护索引树，有一定的性能影响。当频繁维护树B时，分页和整合会产生大量的索引碎片，同时需要维护索引的有效性；但存在一个问题也需要注意。

在一段时间内发生索引（主要是添加、修改、删除数据。如果页面已经完成，则需要对页面进行分割，频率分开，导致索引碎片增多），从而导致索引页面分割。这样会导致随机访问I/O文件，而不是按照I/O的顺序进行读取，所以对索引的访问速度会比较慢。如果碎片数量太多，数据库可能不会使用索引（太慢，数据库会选择更高效的执行计划）。

如何更好地使用数据库索引

索引字段非常小，最好有一个值，如整个值，如INT；对于经常变化的字段，尽量不要创建索引，索引管理成本很高，生成索引碎片比较容易；如定期索引管理，修正索引碎片；不创建或维护不必要的重复索引，会增加数据变化（添加、修改、删除）的成本。使用唯一的高字段创建索引，不能在弱字段如楼层中创建索引。

在SQL句子In中，尽量不要使用函数、运算符或表达式来计算where，这可能会导致索引的错误使用；必须避免在子空间语句中包含空值，否则会导致引擎在表被完全扫描时停止使用索引；你应该避免在句子中使用任何! =或<<，否则会导致引擎停止使用索引来扫描表。

以上便是我的一些见解和回答，可能不能如您所愿，但我真心希望能够对您有所帮助！不清楚的地方您还可以关注我的头条号“每日精彩科技”我将竭尽所知帮助您！

码字不易，感觉写的还行的话，还请点个赞哦！

目录结构数据一定少于内容数据

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

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

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

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

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

值得注意的是，索引是以字段为基础建立的，在检索的时候，如果对被索引的字段进行运算，就很可能打乱事前排好的顺序，导致不得不遍历数据，使索引失去效果。

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

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

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

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

以空间换时间