MySQL 索引方式

标签: mysql 索引 | 发表时间:2016-06-14 09:53 | 作者:
出处:http://m635674608.iteye.com
本文配图来自《高性能MySQL(第二版)》。

在数据库中,对性能影响最大的几个策略包括数据库的锁策略、缓存策略、索引策略、存储策略、执行计划优化策略。
索引策略决定数据库快速定位数据的效率,存储策略决定数据持久化的效率。
MySQL中两大主要存储引擎MyISAM和InnoDB采用了不同的索引和存储策略,本文将分析它们的异同和性能。

MySQL主要提供2种方式的索引:B-Tree(包括B+Tree)索引,Hash索引。
B树索引具有范围查找和前缀查找的能力,对于N节点的B树,检索一条记录的复杂度为O(LogN)。
哈希索引只能做等于查找,但是无论多大的Hash表,查找复杂度都是O(1)。
显然,如果值的差异性大,并且以等于查找为主,Hash索引是更高效的选择,它有O(1)的查找复杂度。如果值的差异性相对较差,并且以范围查找为主,B树是更好的选择,它支持范围查找。


Hash索引各种引擎大同小异,没有太多可探讨性,本文主要讨论不同形式的B树索引。

B树属于二叉平衡树,平衡树就是任何一个节点的左右节点高度差距不能超过1的树,这才是绝对平衡的树。
平衡树比较好的算法是AVL,它通过左旋、右旋及其组合的操作可以保证树绝对平衡。
下面是AVL算法中的全部旋转操作:

平衡树处在任何一个左边的不平衡状态都可以通过相应的旋转操作转移到右边的平衡状态。

数据库采用的B树只在叶子节点记录信息,非叶子节点记录的是范围信息,这是与一般搜索树不同的地方(一般搜索树非叶子节点也记录信息)。
这是一个B+树的结构,InnoDB的索引都采取了这种形式,它在B-树的基础上为每个叶子节点加了一个指针指向下一个叶子节点,这样可以快速的进行范围查找。
MyISAM是否也是B+树我还不能确定,但是B-树我没有想到可以快速进行范围查找的方法,应该也是B+树。


例如这个B+树的例子:

如 果我要查找名字以A开头的全部信息,我只要获取第一个叶子节点,然后顺序沿着指向下一个叶子的指针,直到发现当年叶子节点已经不是以A开头则中止,这样只 要搜索到第一个叶子节点(O(LogN))再沿着指针检索(O(N)),就可以获取全部索引,如果N个节点的表扫描M个连续值,就是 O(LogN)+O(M),如果B-树则需要回溯到上层节点,这样最差的效率是O(LogN)*M。

对于InnoDB,使用了一种改进的B+树索引,称为聚集索引(Clustered Index),它的不同之处在于索引上不仅有索引值的信息,还有整个索引值所在行的信息,免去了一次通过索引值上的位置去取整行的操作。


假 设我们有个表有(col1,col2)列,col1是主键,col2也建立索引。那么在MyISAM引擎中,文件会被这样记录,因为MyISAM是按插入 顺序把数据写入文件。如果有删除则空出位置,再次插入如果可以放下则会填充空白,对于不定长的行,存储引擎都会在分页中预留位置,以供更新更长的值(一般 是VARCHAR),放不下则会添加到文件结尾,并从原位置删除。所以有时候会有空间浪费,需要Optimize Table来优化。
因此:定长的行比不定长的行效率高!把定长数据和不定长数据分开存储,很多时候可以提高效率。


再来看MyISAM的主键索引,索引Key是主键值,索引Value是行的文件位置,通过这个位置可以直接读取行。从这个图上来看,MyISAM也是采用B+树。


MyISAM的非主键索引,跟逐渐索引没有不同,也是索引行的文件位置。


再看InnoDB的主键索引,索引Key是主键值,索引Value是整行的数据。


InnoDB的非主键索引,索引Key是列值,索引Value是主键值。


对比MyISAM和InnoDB的索引策略:

可以发现MyISAM所有列的索引都是一样,索引Key是列值,索引Value是行的文件位置。
InnoDB的主键索引包含了行的全部信息,索引Key是主键值,索引Value是整行的值。而非主键索引索引Key是列值,索引Value是主键值,取数据时到主键索引中取。

并且在InnoDB中,一个聚集索引是必须的,如果没有定义主键,InnoDB也会自己隐含的建立一个聚集索引作为主键,因为InnoDB的主键索引还有个重要的功能就是行锁,这在我的 另一篇文章中分析过。

再来看看我们插入值时会发生什么:

InnoDB会按主键索引顺序组织文件,如果按主键顺序插入,可以直接在最尾部加入。并且只填充页面的15/16,这样可以预留部分空间以供行修改,这样组织的数据是非常紧凑的。

如果主键不是顺序的,我们来看看会发生什么,因为要按主键顺序存放,数据会被不断地移动,调整页面。

所以:InnoDB引擎按主键顺序插入记录是非常必要的,否则性能将会面临很大风险。
 
http://blog.csdn.net/habout632/article/details/7611111


已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [mysql 索引] 推荐:

[MySQL] B+树索引

- - CSDN博客推荐文章
B+树是一种经典的数据结构,由平衡树和二叉查找树结合产生,它是为磁盘或其它直接存取辅助设备而设计的一种平衡查找树,在B+树中,所有的记录节点都是按键值大小顺序存放在同一层的叶节点中,叶节点间用指针相连,构成双向循环链表,非叶节点(根节点、枝节点)只存放键值,不存放实际数据. 保持树平衡主要是为了提高查询性能,但为了维护树的平衡,成本也是巨大的,当有数据插入或删除时,需采用拆分节点、左旋、右旋等方法.

mysql 索引技巧

- - 小彰
MySQL索引的建立对于MySQL的高效运行是很重要的. 下面介绍几种常见的MySQL索引类型. 在数据库表中,对字段建立索引可以大大提高查询速度. 假如我们创建了一个 mytable表:. CREATE TABLE mytable(   ID INT NOT NULL,    username VARCHAR(16) NOT NULL  );   我们随机向里面插入了10000条记录,其中有一条:5555, admin.

mysql选择索引

- - CSDN博客数据库推荐文章
1、尽量为用来搜索、分类或分组的数据列编制索引,不要为作为输出显示的数据列编制索引. 最适合有索引的数据列是那些在where子句中数据列,在联结子句中出现的数据列,或者是在Group by 、Order by子句中出现的数据列. select 后的数据列最好不要用索引. 2、综合考虑各数据列的维度.

mysql 索引详解

- - 行业应用 - ITeye博客
本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题. 特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等. 为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论.

mysql索引认识

- - 数据库 - ITeye博客
数据在磁盘中是以 “块”的形式存储的,所以一张表涉及的数据可能会存在多个块中,而在磁盘中查询数据则会根据字段是否为有序与无序来区分,. 无序情况:1.数值具有唯一性则需要查找 总块数/2.                   2.无序+无唯一性则需要查找  总块数. 有序情况:1.数值唯一性:log2(总块数/2)   (log2是二分查找算法).

MySQL 索引方式

- - zzm
本文配图来自《高性能MySQL(第二版)》. 在数据库中,对性能影响最大的几个策略包括数据库的锁策略、缓存策略、索引策略、存储策略、执行计划优化策略. 索引策略决定数据库快速定位数据的效率,存储策略决定数据持久化的效率. MySQL中两大主要存储引擎MyISAM和InnoDB采用了不同的索引和存储策略,本文将分析它们的异同和性能.

MySql索引总结

- - 掘金后端
MySQL 索引底层数据结构.   Mysql索引使用的数据结构主要有 BTree索引 和 Hash索引. 对于Hash索引来说,底层数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,使用Hash索引查询性能最快. 其余大多数场景建议使用BTree索引. 为什么索引能够提高查询速度.

MySQL InnoDB B+树索引

- - OurMySQL
B+树索引在DB中有一个特点就是高扇出性,一般在DB中B+树的高度在2-3层左右,也就意味着只需要2-3次的IO操作即可. 而现在的磁盘每秒差不多在100次IO左右,2-3次意味着查询时间只需0.02-0.03秒. InnoDB存储引擎表是索引组织表,即表中数据安装主键顺序存放. 而聚集索引就是按照每张表的主键构造一颗B+,并且叶节点存放着整张表的行记录数据,因此也让聚集索引也是索引的一部分.

[转] Mysql索引的问答

- - 数据库 - ITeye博客
相信很多人对于MySQL的索引都不陌生,索引(Index)是帮助MySQL高效获取数据的数据结构. 因为索引是MySQL中比较重点的知识,相信很多人都有一定的了解,尤其是在面试中出现的频率特别高. 楼主自认为自己对MySQL的索引相关知识有很多了解,而且因为最近在找工作面试,所以单独复习了很多关于索引的知识.

MySQL B+树索引及索引优化

- - 数据库 - ITeye博客
    MySQL的索引实现由很多种实现,包括hash索引,B+索引,全文索引等,本文只讨论B+树索引. 1.评价一个索引好坏主要看IO的访问次数,B+树红黑树来说,树高很小(出度很大)即可以有效降低IO的访问次数. B+数的高度h=logd(n),d越大,h越小,查询效率越高. 相对B树,B+树d可以很大,因为非叶子节点不存储数据,只存储key,在一个存储页上可以存储更多的key值.