mysql索引 底层数据结构与算法

mysql索引 底层数据结构与算法

Mysql索引的底层数据结构

首先想清楚，什么是索引？它是一种查询高效、排好序的数据结构！
常见的索引数据结构有：二叉树、红黑树、Hash表、B-Tree，mysql 索引的默认数据结构式是B+Tree，这是B-Tree的一个变种。
更深入地了解，我们需要区分几种数据结构的不同与优劣，这样才能明白为什么要选择B+Tree作为默认的索引结构。
区分不同索引结构

• 二叉树
  

二叉树最坏的情况，所有的节点都在左侧，或者都在右侧。这样的单边增长，会让树的高度非常大，检索效率极低

• 红黑树
  

红黑树能够一定程度上自平衡，无法控制其深度。大数据量下可能左右树倾斜严重，mysql查询的数据如果恰好是子节点，则查询速度会十分地缓慢
红黑树推荐文章：# 最易懂的红黑树讲解

• B-Tree
  

观察上图可以发现B-Tree的一些特点：叶子节点具有相同的高度、节点中索引数据从左到右递增

• B+Tree
  

对比B-Tree可以发现：B+Tree非叶子节点不存储数据，在叶子节点中包含了所有的索引数据。这样做的目的是，在固定大小的节点空间内能够存储更多的索引（对应存储更多的叶子节点数据）
另外，叶子节点之间前后以指针链接，这样访问后续叶子节点中的数据更加高效

• Hash表
  

hash表的查询效率比B+Tree更高效，只需要一次hash计算就能定位到数据；
但是hash只能支持等值查询，如“=”、“in”，无法进行范围查询，此外存在hash冲突问题
区分Innodb与myisam存储引擎

MyISAM索引文件和数据文件是分离的(非聚集)，而Inonodb索引和数据在同一个文件中。

Innodb存储引擎中的一些特点：
表数据存储结构完全符合B+Tree的特点，数据只存储在聚集索引的叶子节点中。
区分是否聚集索引，就看索引和数据是否分离，辅助索引查询后根据主句ID，回表查询聚集索引。
为什么建表时必须建主键？
若是建表时没有建立主键，1.mysql会选择一列没有重复数据的作为主键，2.若不存在这样的列，则生成一个类似行号的作为主键。
这样无规则的字段作为主键是非常影响效率的。
推荐以整型自增主键，好处是方便比较大小，查询效率更高。
联合索引和最左前缀原则

创建联合索引的语法：key indexName (field1,field2,field3....) [using btree]
该索引树将依次按照字段1、字段2、字段3来排序。在索引树的叶子节点中包含了联合索引的所有字段，以及主键ID
最左前缀： 联合索引只能从左往右的顺序依次索引，跳过则后续索引失效。
索引覆盖： 若查询所需字段都包含在联合索引中，则辅助索引无需回表

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除