⑶除根结点之外的所有非终端结点至少有,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针

在B-Tree中按key检索数据的算法非常直观,B-Tree是一个非常有效率的索引数据结构,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,⑴树中每个结点至多有m 棵子树,⑶除根结点之外的所有非终端结点至少有,⑴树中每个结点至多有m 棵子树,一棵m 阶的B-树,⑴树中每个结点至多有m 棵子树,⑶除根结点之外的所有非终端结点至少有

图片 1

数据库索引的特点:

  • 避免进行数据库全表的扫描,大多数情况,只需要扫描较少的索引页和数据页,而不是查询所有数据页。而且对于非聚集索引,有时不需要访问数据页即可得到数据。
  • 聚集索引可以避免数据插入操作,集中于表的最后一个数据页面。
  • 在某些情况下,索引可以避免排序操作。
带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。

图片 1

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

根据磁盘存取原理(主存存取原理不影响)、局部性原理与磁盘预读可知,一般使用磁盘I/O次数评价索引结构的优劣。
数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:
每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。
B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(logd
N)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

B+树

      B+树是应文件系统所需而产生的一种B-树的变形树。一棵m 阶的B+树和m
阶的B-
树的差异在于:
⑴有n 棵子树的结点中含有n 个关键码;
⑵所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且
叶子结点本身依关键码的大小自小而大的顺序链接。
⑶所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。

 

 

 如图一棵3阶的B+树:

图片 2

                                图4.2(c)

 如果因此使双亲结点中的关键字数目小于ceil(m/2)-1,则依次类推。

[例如],在 图4.2(c)的B-树中删去关键字37之后,双亲b结点中剩余信息(“指针c”)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中,删除后的B树如图 4.2(d)所示。
 
图片 3 

 

B-树主要应用在文件系统

为了将大型数据库文件存储在硬盘上
以减少访问硬盘次数为目的 在此提出了一种平衡多路查找树——B-树结构
由其性能分析可知它的检索效率是相当高的 为了提高 B-树性能’还有很多种B-树的变型,力图对B-树进行改进,如B+树。

 

1. MyISAM索引实现:

1)主键索引:

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图:
图片 4

 

                                                                          
(图myisam1)

这里设表一共有三列,假设我们以Col1为主键,图myisam1是一个MyISAM表的主索引(Primary
key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

2)辅助索引(Secondary key)

在MyISAM中,主索引和辅助索引(Secondary
key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。
如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

图片 5

同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

MySQL的B-Tree索引(技术上说B+Tree)

       在 MySQL
中,主要有四种类型的索引,分别为: B-Tree 索引, Hash 索引, Fulltext
索引和 R-Tree 索引。我们主要分析B-Tree 索引。

        B-Tree 索引是 MySQL
数据库中使用最为频繁的索引类型,除了 Archive
存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1
才支持索引,而且只支持索引单个 AUTO_INCREMENT 列。

       不仅仅在 MySQL
中是如此,实际上在其他的很多数据库管理系统中B-Tree
索引也同样是作为最主要的索引类型,这主要是因为 B-Tree
索引的存储结构在数据库的数据检索中有非常优异的表现。

     一般来说,
MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree
的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf
Node(叶子节点) ,而且到任何一个 Leaf Node
的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree
索引。当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree
索引的时候会对存储结构稍作改造。如 Innodb
存储引擎的 B-Tree 索引实际使用的存储结构实际上是
B+Tree
,也就是在 B-Tree
数据结构的基础上做了很小的改造,在每一个Leaf Node
上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node
相邻的后一个 LeafNode
的指针信息(增加了顺序访问指针),这主要是为了加快检索多个相邻 Leaf Node
的效率考虑。

 

下面主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式:

B树(Balance Tree)

又叫做B- 树(其实B-是由B-tree翻译过来,所以B-树和B树是一个概念)
,它就是一种平衡多路查找树。下图就是一个典型的B树:

graph TD
a(M)-->b(E - F)
b-->E
b-->F
a-->c(P - T - X)
E-->d(1 - 2)
F-->e(4 - 5)
缺点
  • 创建索引维护索引要耗费时间,当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。

MySQL的B-Tree索引(技术上说B+Tree)

       在 MySQL 中,主要有四种类型的索引,分别为:
B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree
索引。我们主要分析B-Tree 索引。

        B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive
存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。Archive 引擎直到
MySQL 5.1 才支持索引,而且只支持索引单个 AUTO_INCREMENT 列。

       不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中B-Tree
索引也同样是作为最主要的索引类型,这主要是因为 B-Tree
索引的存储结构在数据库的数据检索中有非常优异的表现。

     一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree
的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf
Node(叶子节点) ,而且到任何一个 Leaf Node
的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree
索引。当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree
索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree
索引实际使用的存储结构实际上是 B+Tree
,也就是在 B-Tree
数据结构的基础上做了很小的改造,在每一个Leaf Node
上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node
相邻的后一个 LeafNode
的指针信息(增加了顺序访问指针),这主要是为了加快检索多个相邻 Leaf Node
的效率考虑。

 

下面主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式:

2. InnoDB索引实现

然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同.

1)主键索引:

         MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB
中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此
InnoDB表数据文件本身就是主索引。

图片 6

 

               (图inndb主键索引)

(图inndb主键索引)是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引
因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选
择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型
为长整形。

2). InnoDB的辅助索引

     
 InnoDB的所有辅助索引都引用主键作为data域。例如,下图为定义在Col3上的一个辅助索引:

图片 7

        InnoDB 表是基于聚簇索引建立的。因此InnoDB
的索引能提供一种非常快速的主键查找性能。不过,它的辅助索引(Secondary
Index,
也就是非主键索引)也会包含主键列,所以,如果主键定义的比较大,其他索引也将很大。如果想在表上定义
、很多索引,则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。

     
文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

     
不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主
键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB
数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为
主键则是一个很好的选择。

 InnoDB索引MyISAM索引的区别:

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

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

(转载出处:) B-树 1
.B-树定义 B-树是一种平衡的多…

B+树

      B+树是应文件系统所需而产生的一种B-树的变形树。一棵m 阶的B+树和m 阶的B-
树的差异在于:
⑴有n 棵子树的结点中含有n 个关键码;
⑵所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且
叶子结点本身依关键码的大小自小而大的顺序链接。
⑶所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。

 如图一棵3阶的B+树:

图片 8

通常在B+树上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算:一种是从最小关键字起顺序查找,另一种是从根节点开始,进行随机查找。 

在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时,若非终端结点上的关键码等于给定值,并不终止,而是继续向下直到叶子结点。因此,在B+
树,不管查找成功与否,每次查找都是走了一条从根到叶子结点的路径。