澳门搏彩官方网 > 操作系统 >

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

澳门平台游戏注册 1

mysql索引: 是一种帮助mysql高效的获取数据的数据结构,这些数据结构以某种方式引用数据,这种结构就是索引。可简单理解为排好序的快速查找数据结构。如果要查“mysql”这个单词,我们肯定需要定位到m字母,然后从下往下找到y字母,再找到剩下的sql。

B+树在数据库中的应用

1.1:索引分类

{

单值索引:一个索引包含1个列 create index idx_XX on table 一个表可以建多个。 唯一索引: 索引列的值必须唯一,但允许有空值 create unique index idx_XX on table 复合索引: 一个索引包含多个列 如:create index idx_XX on table

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

1.2:索引结构

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

BTree Hash索引 full-text全文索引:

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

1.3:什么情况建立索引

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

主键自动建立唯一索引 频繁作为查询条件的字段因该创建索引 查询中与其他表关联的字段,外键关系建立索引 频繁更新的字段不适合建立索引 where条件里用不到的字段不建立索引 单键/复合索引的选择 查询中排序的字段因建立索引 查询中统计或分组字段

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

1.4:什么情况建不建立索引

InnoDB 与 MyISAM 结构上的区别

频繁增删改的表 表记录太少 数据重复且分布平均的表字段。(重复太多索引意义不大)

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

2.1:B+树在数据库索引中的应用

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

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

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

1)在数据库索引的应用

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

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

InnoDB索引和MyISAM索引的区别:

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

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

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

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

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

}

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

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

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

澳门唯一官方网站,在数据库系统的使用过程当中,数据的查询是使用最频繁的一种数据操作。

2.2: 索引在数据库中的作用

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

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

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

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

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

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

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

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

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

2.3:为什么使用B-Tree

1)在数据库索引的应用

澳门平台游戏注册,1.文件很大,不可能全部存储在内存中,故要存储到磁盘上

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

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

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

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

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

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

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

二叉查找树进化品种的红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。

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

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/+Tree,还跟磁盘存取原理有关。

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

局部性原理与磁盘预读

为什么使用B-Tree(B+Tree)

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

二叉查找树进化品种的红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。

当一个数据被用到时,其附近的数据也通常会马上被使用。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/+Tree,还跟磁盘存取原理有关。

程序运行期间所需要的数据通常比较集中。

局部性原理与磁盘预读

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

预读的长度一般为页的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

  • 当一个数据被用到时,其附近的数据也通常会马上被使用。
  • 程序运行期间所需要的数据通常比较集中。

我们上面分析B-/+Tree检索一次最多需要访问节点:

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

h =

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

澳门平台游戏注册 2

我们上面分析B-/+Tree检索一次最多需要访问节点:

数据库系统巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B- Tree还需要使用如下技巧:

h =

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

数据库系统巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B- Tree还需要使用如下技巧:

下一篇:没有了