MySQL-索引的数据结构

MySQL-索引的数据结构

起男 1,138 2021-01-13

MySQL-索引的数据结构

索引分类与引擎对索引的支持

索引是在MySQL的存储引擎层中实现的,而不是在服务器层实现的。所以每种存储引擎的索引都不一定完全相同,也不是所有的存储引擎都支持所有的索引类型。

MySQL目前提供了4中索引:

  • b tree索引:最常见的索引类型,大部分索引都支持b树索引
  • hash索引:之一memory引擎支持,使用场景简单
  • r-tree索引(空间索引):空间索引是MyISAM引擎的一个特殊索引类型,主要用于地图空间数据类型,通常使用较少
  • full-text(全文索引):全文索引也是MyIsam的一个特殊索引类型,主要用于全文索引,innodb从MySQL5.6开始支持全文索引

存储引擎对索引的支持情况

索引inndbmyisammemory
b tree支持支持支持
hash不支持不支持支持
r-tree不支持支持不支持
full-text5.6版本后支持支持不支持

我们常说的索引没有特别的说明,都是指b+树(多路搜索树,并不一定的二叉的)结构组织的索引。其中聚集索引、符合索引、前缀索引、唯一索引默认都是使用b+tree,统称索引

b tree结构

b树又叫多路平衡搜索树,一颗m叉的b tree特性如下:

  • 树中每个节点最多包含m个孩子节点
  • 除根节点与叶子节点外,每个节点至少有[ceil(m/2)]个孩子节点
  • 若根节点不是叶子节点,则至少有两个孩子
  • 所有的叶子节点都在同一层
  • 每个非叶子节点由n个key与n-1个指针组成,其中[ceil(m/2)-1] <=n<=m-1

b+tree结构

b+树是b树的变种,b+树于b树的区别为:

  • n叉b+树最多含有n个key,而b树最多只能含有n-1个key
  • b+树的叶子结点保存所有的key信息,依照key的大小排序
  • 所有的非叶子节点都可以看作key的索引部分

原文:https://mp.weixin.qq.com/s/VUYse9nc8kq2qr_nIlwglQ