目录

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支持的索引
  • 用来保存地理位置数据，如经纬度