本文出自明月工作室:https://www.freebytes.net/it/java/mysql-search-index.html

本文主要参考自: https://zhuanlan.zhihu.com/p/113917726

为什么需要索引？

假设有1000条数据，id是1、2、3、…1000，如果没有索引，那么查找id=1000的记录，需要从1到1000遍历所有记录，查找效率极低。

怎样的数据结构适合做索引

很多种数据结构都作为索引的底层结构，但是MySQL选用了B+树。下面比较下将各种数据结构用作索引的优缺点。

一、哈希表

将id为1~1000全部用hash算法计算好值，hash(1)、 hash(2)、hash(3) … hash(1000)，这样子，当搜索id=1000的记录，只需要直接计算hash(1000)，也就是搜索一次。效率上可谓大大提高。

但是，哈希表有个缺点，就是容易产生碰撞，hash(100)和hash(200)的值可能是相同的。比如原来是用一个数组将hash(1)到hash(1000)的值存储起来的，那么发生碰撞之后，只能将碰撞的元素转为链表存储，就像jdk中HashMap的实现一样。甚至还能将这链表转为红黑树，进一步缩短查找时间。

这样子，貌似哈希表也挺适合用来做mysql的索引底层数据结构的，但是这种查找只是最简单的查找方式，id=1000，id=10；如果是id>100，这样的范围查找，哈希表无能为力。

二、二叉查找树

二叉查找树也叫二叉排序树，是数据结构中的一类，在一般情况下，查询效率比链表结构要高。 它具有以下性质：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树 ；
（4）没有键值相等的结点。

如上图，二叉查找树，同一节点下，其左子树必定比右子树的值小，于是查找id>10这样的数据，直接找到10节点下的右子树即可。这样就解决了范围查找的问题，对于id=10这样的简单查找，其效率比起直接遍历搜索也提升了一半。

但是二叉查找树，容易出现极端的情况，如下图：

这样会导致，查找id=4这样的记录，相当于还是要直接遍历。所以，承载mysql索引的数据结构，还应该具备避免这种极端情况出现的性质。

三、红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

• 性质1：每个节点要么是黑色，要么是红色。
• 性质2：根节点是黑色。
• 性质3：每个叶子节点（NIL）是黑色。
• 性质4：每个红色结点的两个子结点一定都是黑色。
• 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

这些性质，都是为了避免出现上述图中二叉查找树的极端情况，并且尽量使得二叉树平衡，减少搜索深度，提升搜索效率。

红黑树自身，可以在插入、删改节点值时，通过左旋转或右旋转和变色的方式调节自身，使得其满足上述5大性质，成为一颗尽量平衡的二叉树。

红黑树解决了普通二叉查找树的极端问题，但是由于数据库中的基本主键都是自增的，会导致整个红黑树出现“右倾”现象，如：

尽管这个问题可以用更为严格的平衡二叉树AVL树来解决（一个绝对平衡的二叉树），但是 AVL 树并不适合做 Mysql 数据库的索引数据结构，因为考虑一下这个问题：

数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=7 这个数据我们就要进行磁盘 IO 三次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。

https://zhuanlan.zhihu.com/p/113917726

四、B 树和B+树

B 树和B+树都是一种多路平衡查找树，包括一些特定的规则，这些规则主要是为了使得查找树能够尽量平衡并减少查找深度。

B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。其性质如下：

• 根节点至少有两个子节点
• 每个节点最多有M-1个key，并且以升序排列
• 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
• 其它节点至少有M/2个子节点

下图是一个M=4 阶的B树:

B 树和 B+树有什么不同呢？

第一，B 树一个节点里存的是数据，而 B+树存储的是索引（地址），所以 B 树里一个节点存不了很多个数据，但是 B+树一个节点能存很多索引，B+树叶子节点存所有的数据。

第二，B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。

B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

https://zhuanlan.zhihu.com/p/113917726

Innodb 引擎和 Myisam 引擎

MyISAM 虽然数据查找性能极佳，但是不支持事务处理。Innodb 最大的特色就是支持了 ACID 兼容的事务功能，而且他支持行级锁，性能不如MyISAM。

一、MyISAM 引擎

MyISAM 用的是非聚集索引方式，即数据和索引落在不同的两个文件上。MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

二、Innodb引擎

InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，如左下图所示，而 B+树的叶子节点存储的是主键 ID 对应的数据，比如在执行 select * from user_info where id=15 这个语句时，InnoDB 就会查询这颗主键 ID 索引 B+树，找到对应的 user_name=’Bob’。

这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因。

当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY。注意，叶子存储的是主键 KEY！拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

问题来了，为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据，但是其他索引树却不存具体数据呢，而要多此一举先找到主键，再在主键索引树找到对应的数据呢?

其实很简单，因为 InnoDB 需要节省存储空间。一个表里可能有很多个索引，InnoDB 都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得非常巨大（数据极度冗余了）。从节约磁盘空间的角度来说，真的没有必要每个字段索引树都存具体数据，通过这种看似“多此一举”的步骤，在牺牲较少查询的性能下节省了巨大的磁盘空间，这是非常有值得的。