1. InnoDB存储引擎索引概述

主要有两种：

• B+树索引（不能找到具体行，找到的是具体列）
• 哈希索引

2. 二分查找法

3. 平衡二叉树

3.1 二叉查找树

• 左子树小于根的值，右子树大于根的值
• 可以通过中序遍历输出：2、3、5、6、7、8
• 查找某个值，先跟根元素判断，如果根小，去右子树；如果根大，去左子树
• 二叉查找树可以任意构造，如下面：
  

3.2 平衡二叉树

• 任何节点左右两个子树的高度，最大差为1
• 性能是比较高的，如果需要最好的性能，需要最优二叉树，但是建立和维护需要很大的操作
• 插入数据后，需要左旋或者右旋维护平衡性
  

<mark>左旋</mark>

<mark>右旋</mark>

3.3 B+树

• 为磁盘或其他直接存取的辅助设备而设计的平衡二叉树
• 所有的记录节点都是按照键值的大小顺序存放在同一层的叶节点
  

3.3.1 B+树插入算法

• index Page上面存放了，子页的第一个节点
  
  实例1
  实例2

• 插入70时，发现left page已满，index page没有满
  

• 拆分left page，将其中间节点放在index page，小于中间节点的放在左边，大于中间节点的，放在右边

实例3

• 再插入95时，发现left page和index page已满，需要进行两次拆分

旋转

• 如果兄弟没有满，可以优先将数据移到兄弟节点，减少分页
  

3.3.2 B+树删除操作

• 使用填充因子控制树的删除变化，50%是其最小值
  

实例1

实例2

• 删除25时，由于25在index page，删除后小于50%，将25的兄弟28补充到原来25的位置
  实例3
• 删除60时，此时leftpage仅剩65，所以需要将65和并到兄弟节点，同时合并index page
  

3.5 B树和B+树的区别

B树

• 所有的节点都会存储数据
• 父节点当中的索引不会出现在子节点中
  

B+树

• 只在叶子节点存储数据
• 父节点当中的索引会出现在子节点中
• 叶子节点中的最后一个索引会指向下一个叶子节点的第一个索引

B+树相对于B树有一些自己的优势，可以归结为下面几点。

• 单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了。
• 所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定。
• 所有的叶子节点形成了一个有序链表，更加便于查找。

4. B+树索引

• 分为聚集索引和辅助聚集索引
• 不需要再进行全表查找，对树进行查找即可，速度很快
• 是有序的，可以用于排序和分组

4.1 聚集索引(主键索引)

• 按照主键构造B+数，页节点放的是完整行数据
• 一个表只能有一个（如果没有主键，就会自动创建一个rowid作为主键索引）
• 对主键的排序查找和范围查询速度特别快，如查询前十条数据和查询大于5的数据

为什么建议使用主键索引？

• 表的存储结构： 表空间 段（索引 = 索引段 + 数据段） 区 = 1M = 64 页 页（16K，叶子节点）
• 非自增的情况下，插入数据其他需要移动位置、页分裂、B+树结构的调整的、由于无法判断数据放在哪里，磁盘利用率很低，如插入一条ID为250的数据
  
• 自增的好处是：磁盘利用率高，不会导致其他索引的移动

为什么使用整型做索引而不是字符串？

• 字符串的空间太大，浪费了大量空间，导致B+树出度变小
• 整型的空间占的小
• ·方便排序·

4.2 辅助索引（非主键索引）

• 子节点不包括全部行数据
• 包含的是一个书签，告诉InnoDB引擎去哪里找数据，对应的就是聚集索引的主键

为什么只存储主键？

• 空间上：存储多余的数据浪费磁盘空间
• 时间上：对索引的更新更慢

MyISAM存储的是磁盘地址

• MyISAM生成三个文件：user.myi 索引文件、user.myd数据文件 、user.frm数据结构类型。
• 默认没用生成主键的索引树，所以就没有在索引中存储地址

4.3 索引的管理

• ALTER TABLE

alter table  表名  add [index/key]  索引名 (列名)
alter table  表名   drop   [index/key]  索引名

• CREATE /DROP INDEX

• 对于非聚集索引，创建索引时会对表加一个S锁，此时只能读数据

4.3 B+树索引的使用

• 如果数据选择性很高，且只取其中一部分时，即身份证号，电话号等，可以加索引，但是像性别，地区等，不建议加索引
• 如果高选择性，但是要取其中大部分数据时，不建议使用
• 优化器在判断是否返回的行数很多，如果很多，自动不使用索引
• 如果查询经常使用 where xxx = xxx and xxx =xxx 时，可以使用联合索引
• 联合索引会自动对每个列排好序

4.4 B+树索引和红黑树的比较

更少的查找次数
查找速度跟树h有关

• 红黑树的兄弟节点最多一个，所以H很高
• B+树兄弟节点可以有多个，多以H很低

可以利用磁盘的预读特性
磁盘读取数据是，会把相邻节点数据提前载入，B+树每个节点存储着不止一个数据，磁盘读取速度快

5 哈希索引

• InnoDB的自适应哈希索引使用的散列表

• 当某些索引值被使用的比较频繁，会在B+树索引之上建立一个哈希索引

特点：

• 查询速度是O(1)的，但是失去了有序性
• 无法用于排序和分组
• 只能进行精确查找（等值查找），不能用于部分查找和范围查找

6. 全文索引

• MySIAM索引支持全文索引，用于查找关键词，同时不单单进行等值匹配，还会根据出现的频率进行匹配

• InnoDB在MySQL 5.6.4以后的版本支持

7. 空间数据索引

• MyISAM支持的索引
• 用来保存地理位置数据，如经纬度