Mysql索引数据结构和算法原理

2017/02/11

Mysql索引 - B树/B+树

介绍

Mysql支持多种存储引擎,每种存储引擎对索引的支持也是不一样的, Mysql数据库支持的索引包括B树 哈希索引 全文索引 本文主要介绍最常用的B树

B树/B+树介绍

B树

《算法导论》对B树定义 - B树是平衡树的一种,主要用于操作存储在磁盘等二级存储设备上的大量数据。相比起内存(主存)来说,磁盘操作的速度非常慢(慢几个数量级),所以涉及到存储在磁盘的数据的时候,尽量减少磁盘的读取和写入操作对于提高操作速度是非常重要的。B树就是针对这个特点进行设计以满足相应要求的。 我们知道二叉树的查找时间复杂度是O(log2N)与树的深度相关,所以减少树的深度就能提高查找速度,B树时间复杂度是O(logdN) 其中d就是树的深度所以d越大时间就越短

B+树

B+树 是B树的变种 他也是Mysql中使用的数据结构 , 一颗B+树包含根节点,内部节点,和叶子节点。它相对于B树有一下几个不同点:

  • 更适合文件索引系
  • 内节点不存储data,只存储key,叶子节点不存储指针
  • 每个节点的指针上限为2d而不是2d+1
  • 所有的关键字都在叶子节点出现
  • B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找

avatar

MylSAM 索引

MylSAM引擎用B+树作为索引的数据结构,叶节点的data域存放的是数据的地址,也叫做非聚集索引

InnoDB 索引

InnoDB 也是用B+树作为数据结构,但是与MylSAM不同是,叶子节点的data域存放的是数据本身,相对的叫做聚集索引,InnoDB的辅助索引都引用主键作为data域,所以这也是不建议使用过长的字段作为主键,因为所有辅助索引都引用主键,过长的索引会另辅助索引变得过大,因为InnoDB是一颗B+树,如果主键不是单调的话,频繁插入更新会导致B+树频繁更新调整,造成碎片

Post Directory