MySQL 索引结构分为4类:B-Tree、R-Tree、Hash、全文索引

2017年04月28日 11:02 分类 : MySQL  > MySQL应用
阅读: 3856

分享到微信朋友圈

【多数 mysql索引(主键,唯一,全文索引)是用B-tree存储的,除了:空间索引R-tree; 内存表也支持hash索引;innodb对全文索引用反向链表】

MySQL 索引结构分为4类:B-Tree、R-Tree、Hash、全文索引


索引数据结构分为:


Most MySQL indexes (PRIMARY KEY, UNIQUE, INDEX, and FULLTEXT) are stored in B-trees. Exceptions: Indexes on spatial data types use R-trees; MEMORY tables also support hash indexes; InnoDB uses inverted lists for FULLTEXT indexes.


【多数 mysql索引(主键,唯一,全文索引)是用B-tree存储的,除了:空间索引R-tree; 内存表也支持hash索引;innodb对全文索引用反向链表】


索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。


从MySQL逻辑架构来看,MySQL有三层架构,第一层连接,第二层查询解析、分析、优化、视图、缓存,第三层,存储引擎。

MySQL 索引结构分为4类:B-Tree、R-Tree、Hash、全文索引


索引通过分开查询片,节省了扫描查找时间,大大提升查询效率。

大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。

索引主要在存储引擎层上,不同的引擎也就有不同的B-Tree算法。


聚簇索引、非聚簇索引 -- 数据存储方式

主要是根据存储引擎来区分数据存储方式,里面在包含 B-tree、等等 索引存储方式


数据库必须有索引,没有索引则检索过程变成了顺序查找,O(n)的时间复杂度几乎是不能忍受的。我们非常容易想象出一个只有单关键字组成的表如何使用B+树进行索引,只要将关键字存储到树的节点即可。当数据库一条记录里包含多个字段时,一棵B+树就只能存储主键,如果检索的是非主键字段,则主键索引失去作用,又变成顺序查找了。这时应该在第二个要检索的列上建立第二套索引。这个索引由独立的B+树来组织。有两种常见的方法可以解决多个B+树访问同一套表数据的问题,一种叫做聚簇索引(clustered index),一种叫做非聚簇索引(secondary index)。这两个名字虽然都叫做索引,但这并不是一种单独的索引类型,而是一种数据存储方式。对于聚簇索引存储来说,行数据和主键B+树存储在一起,辅助键B+树只存储辅助键和主键,主键和非主键B+树几乎是两种类型的树。对于非聚簇索引存储来说,主键B+树在叶子节点存储指向真正数据行的指针,而非主键。


InnoDB使用的是聚簇索引,将主键组织到一棵B+树中,而行数据就储存在叶子节点上,若使用"where id = 14"这样的条件查找主键,则按照B+树的检索算法即可查找到对应的叶节点,之后获得行数据。若对Name列进行条件搜索,则需要两个步骤:第一步在辅助索引B+树中检索Name,到达其叶子节点获取对应的主键。第二步使用主键在主索引B+树种再执行一次B+树检索操作,最终到达叶子节点即可获取整行数据。

MyISM使用的是非聚簇索引,非聚簇索引的两棵B+树看上去没什么不同,节点的结构完全一致只是存储的内容不同而已,主键索引B+树的节点存储了主键,辅助键索引B+树存储了辅助键。表数据存储在独立的地方,这两颗B+树的叶子节点都使用一个地址指向真正的表数据,对于表数据来说,这两个键没有任何差别。由于索引树是独立的,通过辅助键检索无需访问主键的索引树。


为了更形象说明这两种索引的区别,我们假想一个表如下图存储了4行数据。其中Id作为主索引,Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。

MySQL 索引结构分为4类:B-Tree、R-Tree、Hash、全文索引

MySQL 索引结构分为4类:B-Tree、R-Tree、Hash、全文索引

码农百家

精彩评论:0

还可以输入250个字 评论

评论成功

评论失败

 

微信公众号

微博