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-树删除算法

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

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

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

局部性原理与磁盘预读

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

当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，因此对于具有局部性的程序来说，预读可以提高I/O效率。

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

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

h =

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

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

B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存)，渐进复杂度为O(h)=O(logmN)。一般实际应用中，m是非常大的数字，通常超过100，因此h非常小(通常不超过3)。

综上所述，用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

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两个存储引擎的索引实现方式：

1. MyISAM索引实现：

1)主键索引：

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