首页 > 数据库 > mysql教程 > 为什么要用B+树结构MySQL索引结构的实现_MySQL

为什么要用B+树结构MySQL索引结构的实现_MySQL

WBOY
发布: 2016-05-30 17:09:47
原创
967 人浏览过

B+树在数据库中的应用

{

为什么使用B+树?言简意赅,就是因为:

1.文件很大,不可能全部存储在内存中,故要存储到磁盘上

2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数(为什么使用B-/+Tree,还跟磁盘存取原理有关。)

3.局部性原理与磁盘预读,预读的长度一般为页(page)的整倍数,(在许多操作系统中,页得大小通常为4k)

4.数据库系统巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入,(由于节点中有两个数组,所以地址连续)。而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性

InnoDB 与 MyISAM 结构上的区别

1.InnoDB的主键索引 ,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引,所以必须有主键,如果没有显示定义,自动为生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形2.InnoDB的辅助索引(Secondary Index, 也就是非主键索引)也会包含主键列,比如名字建立索引,内部节点 会包含名字,叶子节点会包含该名字对应的主键的值,如果主键定义的比较大,其他索引也将很大3.MyISAM引擎使用B+Tree作为索引结构,索引文件叶节点的data域存放的是数据记录的地址,指向数据文件中对应的值,每个节点只有该索引列的值

4.MyISAM主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,辅助索引可以重复,

(由于MyISAM辅助索引在叶子节点上存储的是数据记录的地址,和主键索引一样,所以相对于B+的InnoDB可通过辅助索引

快速找到所有的数据,而不需要再遍历一边主键索引,所以适用于OLAP)

InnoDB索引和MyISAM索引的区别:

一是主索引的区别,InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别:InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

}

1. 索引在数据库中的作用

在数据库系统的使用过程当中,数据的查询是使用最频繁的一种数据操作。

最基本的查询算法当然是顺序查找(linear search),遍历表然后逐行匹配行值是否等于待查找的关键字,其时间复杂度为O(n)。但时间复杂度为O(n)的算法规模小的表,负载轻的数据库,也能有好的性能。 但是数据增大的时候,时间复杂度为O(n)的算法显然是糟糕的,性能就很快下降了。

好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

索引是对数据库表 中一个或多个列的值进行排序的结构。与在表 中搜索所有的行相比,索引用指针 指向存储在表中指定列的数据值,然后根据指定的次序排列这些指针,有助于更快地获取信息。通常情 况下 ,只有当经常查询索引列中的数据时 ,才需要在表上创建索引。索引将占用磁盘空间,并且影响数 据更新的速度。但是在多数情况下 ,索引所带来的数据检索速度优势大大超过它的不足之处。

2. B+树在数据库索引中的应用

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

1)在数据库索引的应用

在数据库索引的应用中,B+树按照下列方式进行组织 :

① 叶结点的组织方式 。B+树的查找键 是数据文件的主键 ,且索引是稠密的。也就是说 ,叶结点 中为数据文件的第一个记录设有一个键、指针对 ,该数据文件可以按主键排序,也可以不按主键排序 ;数据文件按主键排序,且 B +树是稀疏索引 , 在叶结点中为数据文件的每一个块设有一个键、指针对 ;数据文件不按键属性排序 ,且该属性是 B +树 的查找键 , 叶结点中为数据文件里出现的每个属性K设有一个键 、 指针对 , 其中指针执行排序键值为 K的 记录中的第一个。

② 非叶结点 的组织方式。B+树 中的非叶结点形成 了叶结点上的一个多级稀疏索引。 每个非叶结点中至少有ceil( m/2 ) 个指针 , 至多有 m 个指针 。

2)B+树索引的插入和删除

①在向数据库中插入新的数据时,同时也需要向数据库索引中插入相应的索引键值 ,则需要向 B+树 中插入新的键值。即上面我们提到的B-树插入算法。

②当从数据库中删除数据时,同时也需要从数据库索引中删除相应的索引键值 ,则需要从 B+树 中删 除该键值 。即B-树删除算法

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板