[MySQL]B+树索引

页面导航:首页 > 数据库 > Mysql > [MySQL]B+树索引

[MySQL]B+树索引

来源: 作者: 时间:2016-02-21 09:46 【

[MySQL]B+树索引B+树是一种经典的数据结构,由平衡树和二叉查找树结合产生,它是为磁盘或其它直接存取辅助设备而设计的一种平衡查找树,在B+树中,所有的记录节点都是按键值大小顺
[MySQL]B+树索引
 
B+树是一种经典的数据结构,由平衡树和二叉查找树结合产生,它是为磁盘或其它直接存取辅助设备而设计的一种平衡查找树,在B+树中,所有的记录节点都是按键值大小顺序存放在同一层的叶节点中,叶节点间用指针相连,构成双向循环链表,非叶节点(根节点、枝节点)只存放键值,不存放实际数据。下面看一个2层B+树的例子:
 
 
保持树平衡主要是为了提高查询性能,但为了维护树的平衡,成本也是巨大的,当有数据插入或删除时,需采用拆分节点、左旋、右旋等方法。B+树因为其高扇出性,所以具有高平衡性,通常其高度都在2~3层,查询时可以有效减少IO次数。B+树索引可以分为聚集索引(clustered index)和非聚集索引(即辅助索引,secondary index)。
 
聚集索引
InnoDB表时索引组织表,即表中数据按主键B+树存放,叶子节点直接存放数据,每张表只能有一个聚集索引。
 
辅助索引
辅助索引(也称非聚集索引)是指叶节点不包含行的全部数据,叶节点除了包含键值之外,还包含一个书签连接,通过该书签再去找相应的行数据。下图显示了InnoDB存储引擎辅助索引和聚集索引的关系:
 
 
从上图中可以看出,辅助索引叶节点存放的是主键值,获得主键值后,再从聚集索引中查找整行数据。举个例子,如果在一颗高度为3的辅助索引中查找数据,首先从辅助索引中获得主键值(3次IO),接着从高度为3的聚集索引中查找以获得整行数据(3次IO),总共需6次IO。一个表上可以存在多个辅助索引。
 
索引组织表 VS 堆表
MyISAM中的表是以堆表的方式进行存储,堆表没有主键,因此没有聚集索引,辅助索引叶节点不是返回主键值,而是返回行标志符(ROWID),通过ROWID再去查找相应的行。
很显然,对于堆表来说,通过辅助索引访问更快(IO更少),但是如果在OLTP应用下,表中数据经常被修改,辅助索引中的ROWID可能需要经常更新,如果更新影响到物理地址的更改,这种开销比索引组织表要大得多。
因此,索引组织表还是堆表,这取决于你的应用,如果你的应用是OLAP,数据更新很少,堆表更好一些。
 
 
复合索引
复合索引是指对表上的多个列做索引,下面是一个复合索引的例子:
[sql] 
alter table t add key idx_a_b(a,b);  
 
下图是B+树结构:
 
 
很显然,对于where a = xxx and b=xxx 这样的语句是可以使用这个复合索引的。现在看看对单个列的情况,where a = xxx也是可以使用该复合索引,因为a列在复合索引中也是有序的,但对于where b =xxx 这样的语句是无法使用该复合索引,因为它是无序的。
Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<