1、B-Tree(Balance Tree)

二叉搜索树 -> 平衡二叉树

由于二叉搜索树在不平衡状态下性能较差，提出了平衡二叉树的概念

平衡二叉树 -> B树

对于平衡二叉树来说，树的深度时log2n，查询的时间复杂度是O(log2n)，当树的节点过多时时间复杂度还是过大，于是将二叉树改为M叉树，即B树

image.png

B-Tree特性

  • 根节点的子节点个数2 <= x <= m ，m是树的阶,假设m = 3 ,则根节点可以有2-3个孩子
  • 中间节点的子节点个数m/2 <=y <= m ，假设m = 3 ,中间节点至少有2个孩子,最多3个孩子
  • 每个中间节点包含n个关键字，n=子节点个数-1 ,且按升序排序，如果中间节点有3个子节点,则里面会有2个关键字,且按升序排序
  • 节点如果有n个关键字则有n +1个指针

2、B+ Tree

image.png

B+ Tree是在 B-Tree基础上的一种优化

◆ B+Tree有n个子节点的节点中含有n个关键字，B-Tree是n个子节点的节点有n-1个关键字

◆ B+Tree中,所有的叶子节点中包含了全部关键字的信息,且叶子节点按照关键字的大小自小而大顺序链接,构成一个有序链表，B-Tree的叶子节点不包括全部关键字

◆B+Tree中,非叶子节点仅用于索引,不保存数据记录,记录存放在叶子节点中，B-Tree中,非叶子节点既保存索引,也保存数据记录

B+ Tree对范围查询性能更好
相同空间B+Tree存放的关键字更多，查找次数更少

3、Hash索引

哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
对于hash相同的，采用链表的方式解决冲突。类似于hashmap。因为索引的结构是十分紧凑的，所以hash索引的查询很快


4、空间索引

存储GIS数据,基于R-Tree
MySQL 5.7开始InnoDB支持空间索引

5、全文索引

适应全文搜索的需求
◆MySQL 5.7之前,全文索引不支持中文,经常搭配Sphinx
MySQL 5.7起,内置ngram ,支持中文

rmlam : https://dev.mysql.com/doc/refman/8.0/en/fulltext-search-ngram.html

被搜索引擎代替

6、mysql不同存储引擎的索引结构

InnoDB
B+ Tree
主键索引： 叶子节点存储主键及数据
非主键索引：叶子节点存储索引及主键

支持自适应Hash索引
show variables Like 'innodb_ adaptive_ hash_ index'

MyISAM
主键/非主键索引的叶子节点都是存储指向数据块的指针

Memory
支持显示的Hash索引

7、B-Tree(包括B+ Tree)、Hash索引的特性与限制

B-Tree 索引特性

完全匹配: index(name) => where name = ‘abc’
范围匹配: index(age) => where age > 1
前缀匹配: index(name) = > where name like ‘a%’

B-Tree 索引限制

index(name, age, sex)
●查询条件不包括最左列,无法使用索引 where age=5 and sex=1无法使用索引
●跳过了索引中的列,则无法完全使用索引 where name = ‘大目’ and sex = 32 =>只能用name这- -列
●查询中有某个列的范围(模糊)查询,则其右边所有列都无法使用索引 where name = ‘大目’ and age > 32andsex = 1 =>只能用name、age两列
hash索引特性
一般性能比B-Tree好
hash索引的限制：

  • 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。
  • 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
  • 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
  • 哈希索引只支持等值比较查询，包括=、IN()、<>（注意<>和<=>是不同的操作）。也不支持任何范围查询，例如WHERE price>100。
  • 访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
  • 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。