B+树在数据库中的应用存储在磁盘上2.索引的结构组织应该尽量减少搜索过程中的磁盘I/O访问次数（为什么要使用B-/+Tree也和磁盘访问原理有关。）3.局部性和磁盘预排序原理读，预读的长度一般是页的整数倍（在很多操作系统中，pagesize通常为4k)4.数据库系统巧妙的利用了磁盘预读的原理，将一个节点的大小设置为Onepage，这样每个节点只需要一次I/O就可以满载（因为有节点中的两个数组，地址是连续的）。在红黑树结构中，h显然要深很多。因为逻辑上靠近的节点（父节点和子节点）在物理上可能很远，所以不能使用局部性。InnoDB和MyISAM结构上的区别1.InnoDB的主键索引、MyISAM索引文件和数据文件是分开的，索引文件只保存数据记录的地址。在InnoDB中，表数据文件本身就是一个由B+Tree组织的索引结构，这棵树的叶子节点数据域存储了完整的数据记录。这个索引的键是数据表的主键，所以InnoDB表数据文件本身就是主索引，所以必须有一个主键。如果没有显式定义，则自动生成一个隐式字段作为主键。该字段长度为6字节，类型为长整形2.InnoDB的二级索引（SecondaryIndex，即非主键索引）也会包含主键列，比如名称索引，内部节点会包含名称，叶节点将包含与名称对应的主键的值。如果主键定义比较大，其他索引也会很大。3、MyISAM引擎使用B+Tree作为索引结构。索引文件的叶子节点的data字段存储数据记录的地址，指向数据文件中对应的值。每个节点只有索引列的值4.MyISAM主索引和二级索引（Secondarykey）在结构上没有区别，但是主索引要求key唯一，二级索引可以重复，（因为MyISAM二级索引存储在叶子节点上数据记录的地址与主键索引相同，所以相比B+InnoDB，可以通过辅助索引快速找到所有数据，无需遍历主键索引，所以它适用于OLAP)InnoDB索引和MyISAM索引的区别：一个是主索引的区别，InnoDB数据文件本身就是索引文件。MyISAM索引和数据是分开的。二是辅助索引的区别：InnoDB的辅助索引数据字段存储的是对应记录的主键值，而不是地址。MyISAM二级索引与主索引没有太大区别。}1。索引在数据库中的作用在数据库系统的使用过程中，数据查询是最常用的数据操作。最基本的查询算法当然是线性搜索，它遍历表，逐行匹配行值是否等于要搜索的关键字，其时间复杂度为O(n)。但是，时间复杂度为O(n)的算法对于小型表和轻负载数据库也可以有很好的性能。但是当数据变大的时候，时间复杂度为O(n)的算法显然就不好了，性能会很快下降。幸运的是，计算机科学的发展提供了很多更好的搜索算法，比如二分搜索（binarysearch）、二叉树搜索（binarytreesearch）等等。如果稍微分析一下，你会发现每一种搜索算法只能应用于特定的数据结构。比如二分查找要求检索到的数据是有序的，二叉树查找只能应用于二叉查找树，但是数据本身的组织结构不可能完全满足各种数据结构（比如理论上是不可能同时按顺序组织两个列），因此，数据库系统除了数据之外，还维护了一个满足特定搜索算法的数据结构。结构以某种方式引用（指向）数据，以便可以在这些数据结构上实现高级查找算法。这个数据结构是一个索引。索引是一种对数据库表中一个或多个列的值进行排序的结构。与搜索表中的所有行相比，索引使用指针指向表中指定列中存储的数据值，然后将这些指针按照指定的顺序排列，有助于更快地获取信息。通常情况下，只需要在索引列中的数据被频繁查询时才需要在表上创建索引。索引占用磁盘空间，影响数据更新速度。但在大多数情况下，索引带来的数据检索速度优势大大超过了它的劣势。2、B+树在数据库索引中的应用目前，大多数数据库系统和文件系统都使用B-Tree或其变体B+Tree作为索引结构1）数据库索引的应用在数据库索引的应用中，B+树如下组织方式不同：①叶节点的组织方式。B+树的查找键是数据文件的主键，索引是密集的。也就是说，叶节点中数据文件的第一条记录存在键和指针对，数据文件可以按主键排序，也可以不按主键排序；数据文件按主键排序，B+树为稀疏索引，在叶节点中为数据文件的每个块设置一对键和指针；数据文件不按key属性排序，该属性为B+树的搜索关键字，数据文件中出现叶子节点K的每个属性K都设置了key,指针对，其中指针执行首先对键值为K的记录进行排序。②组织非叶节点。B+树中的非叶子节点在叶子节点上形成多级稀疏索引。每个非叶节点至少有ceil(m/2)个指针，最多有m个指针。2）B+树索引的插入和删除①向数据库中插入新数据时，还需要将对应的索引键值插入到数据库索引中，然后需要向B+树中插入新的键值。也就是我们上面提到的B树插入算法。②从数据库中删除数据时，还需要从数据库索引中删除相应的索引键值，然后需要从B+树中删除该键值。即B树删除算法#p#为什么要用B树（B+Tree）二叉搜索树红黑树等进化品种的数据结构也可以用来实现索引，但是文件系统和数据库系统一般使用B-/+Tree作为索引结构。一般来说，索引本身也很大，不可能全部存储在内存中，所以索引往往以索引文件的形式存储在磁盘上。在这种情况下，索引搜索过程中会产生磁盘I/O消耗。与内存访问相比，I/O访问的消耗要高几个数量级，所以作为指标评价一个数据结构好坏最重要的指标就是磁盘I/O操作次数的渐近复杂度抬头。换句话说，索引结构组织应该尽量减少搜索过程中的磁盘I/O访问次数。为什么要用B-/+Tree也跟磁盘访问的原理有关。局部性和磁盘预读原理由于存储介质的特性，磁盘本身的访问要比主存慢很多。除了机械运动的成本外，磁盘的存取速度往往是主存的百分之一。因此，为了提高效率，尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都提前读取。即使只需要一个字节，磁盘也会从这个位置开始，依次向后读取一定长度的数据到内存中。其理论依据是计算机科学中众所周知的局部性原则：当使用一条数据时，通常会立即使用附近的数据。程序运行过程中需要的数据通常比较集中。由于磁盘顺序读取的效率很高（没有寻道时间，旋转时间很少），预读可以提高具有局部性的程序的I/O效率。预读的长度一般是一页的整数倍。页是计算机管理的内存的逻辑块。硬件和操作系统通常将主内存和磁盘存储区域划分为大小相等的连续块。每个存储块称为页（在许多操作系统中，页大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发缺页异常。这时，系统会向磁盘发送一个读信号，磁盘会找到数据的起始位置，并不断地向后读取一页或几页。载入内存，然后异常返回，程序继续运行。上面我们分析了B-/+Tree的检索最多需要访问的节点：h=数据库系统巧妙地利用了磁盘预读的原理，将一个节点的大小设置为一页，这样每个节点只需要一个输入/输出。完全读取。为了达到这个目的，在B-Tree的实际实现中，需要用到以下技巧：每次创建一个新的节点时，直接申请一个页空间，从而保证一个节点在物理上也有存储在一个页面中，并且计算机存储分配是按页面对齐的，它实现了一个节点只需要一个I/O。B-Tree中一次查找至多需要h-1个I/O（根节点常驻内存），渐近复杂度为O(h)=O(logmN)。在一般的实际应用中，m是一个很大的数，通常超过100，所以h很小（通常不超过3）。综上所述，使用B-Tree作为索引结构是非常高效的。在红黑树结构中，h显然要深很多。由于逻辑上接近的节点（父子节点）在物理上可能很远，无法利用局部性，所以红黑树的I/O渐近复杂度也是O(h)，效率明显比红黑树差很多B树。MySQL的B-Tree索引（技术上是B+Tree）在MySQL中，主要有四种索引，分别是：B-Tree索引、Hash索引、Fulltext索引和R-Tree索引。我们主要分析B-Tree索引。B-Tree索引是MySQL数据库中最常用的索引类型，除了Archive存储引擎之外的所有存储引擎都支持B-Tree索引。Archive引擎直到MySQL5.1才支持索引，并且只支持索引单个AUTO_INCREMENT列。不仅在MySQL中，实际上在很多其他数据库管理系统中，B-Tree索引也是最重要的索引类型，主要是因为B-Tree索引的存储结构在数据库的数据检索中起着重要的作用.很好的表现。一般来说，MySQL中B-Tree索引的物理文件大部分存储在BalanceTree的结构中，即实际需要的所有数据都存储在Tree的LeafNode中，任意一个Leaf的长度Node的最短路径完全一样，所以我们都称它为B-Tree索引。当然，各种数据库（或者MySQL的各种存储引擎）在存储自己的B-Tree索引时，可能会稍微修改一下存储结构。例如Innodb存储引擎的B-Tree索引实际使用的存储结构实际上是B+Tree，即在B-Tree数据结构的基础上做了一个小的修改，存储索引键在每个LeafNode上除了保存LeafNode的相关信息外，还保存了指向与LeafNode相邻的下一个LeafNode的指针信息（增加了顺序访问指针），主要是出于加快效率的考虑检索多个相邻的叶节点。#p#下面主要讨论MyISAM和InnoDB存储引擎的索引实现方法：1.MyISAM索引实现：1）主键索引：MyISAM引擎使用B+Tree作为索引结构，叶子节点存储的数据字段数据记录地址。下图是MyISAM主键索引的示意图：（图myisam1）这里的表一共有三列。假设我们使用Col1作为主键。图myisam1是MyISAM表的主键示意图。可见MyISAM索引文件只保存了数据记录的地址。2）二级键（Secondarykey）在MyISAM中，主索引和二级键（Secondarykey）在结构上没有区别，但是主索引要求键是唯一的，而二级索引的键可以是重复。如果我们在Col2上创建一个辅助索引，这个索引的结构如下图所示：也是一个B+Tree，data字段存放的是数据记录的地址。所以MyISAM中的索引检索算法是先按照B+Tree的查找算法来查找索引。如果指定的Key存在，则取出其数据域的值，然后以数据域的值作为地址，读取对应的数据记录。MyISAM的索引方式也叫“非聚集”，是为了和InnoDB的聚集索引区分开来的。2、InnoDB的索引实现虽然InnoDB也是使用B+Tree作为索引结构，但是具体的实现方式与MyISAM完全不同。1）主键索引：MyISAM索引文件和数据文件是分开的，索引文件只保存数据记录的地址。在InnoDB中，表数据文件本身就是一个由B+Tree组织的索引结构，这棵树的叶子节点数据域存储了完整的数据记录。这个索引的key是数据表的主键，所以InnoDB表数据文件本身就是主索引。(图inndb主键索引)(图inndb主键索引)是InnoDB主索引(也是一个数据文件)的示意图。可以看到叶子节点包含了完整的数据记录。这种类型的索引称为聚簇索引。因为InnoDB的数据文件是按照主键聚合的，所以InnoDB要求表有主键（MyISAM可能没有）。如果没有明确指定，MySQL系统会自动选择一个能够唯一标识数据记录的列作为主键。如果不存在这样的列，MySQL会自动生成一个隐式字段作为InnoDB表的主键。该字段长度为6字节，类型为长整型。2).InnoDB的辅助索引InnoDB的所有辅助索引都将主键作为数据字段。例如下图是定义在Col3上的辅助索引：InnoDB表是基于聚簇索引构建的。因此，InnoDB的索引可以提供非常快速的主键查找性能。但是它的二级索引（SecondaryIndex，即非主键索引）也会包含主键列，所以如果主键定义比较大，其他索引也会很大。如果要在表上定义很多索引，尽量把主键定义得越小越好。InnoDB不压缩索引。文本字符的ASCII码用作比较标准。聚簇索引的实现使得主键查找非常高效，但是辅助索引查找需要两次检索索引：先检索辅助索引获取主键，再使用主键检索其中的记录一级指标。不同存储引擎的索引实现方式对索引的正确使用和优化有很大的帮助。例如，了解了InnoDB的索引实现后，就很容易理解为什么不建议使用太长的字段作为主键，因为所有的辅助索引都引用主索引，太长的主索引会使二级索引太大了。再比如，在InnoDB中使用非单调字段作为主键并不是一个好主意，因为InnoDB数据文件本身就是B+树，非单调主键会导致数据文件维护B+Tree插入新记录时的特性。频繁的拆分调整效率很低，使用自增字段作为主键是一个不错的选择。一是主索引的区别，InnoDB数据文件本身就是索引文件。MyISAM索引和数据是分开的。二是辅助索引的区别：InnoDB的辅助索引数据字段存储的是对应记录的主键值，而不是地址。MyISAM二级索引与主索引没有太大区别。
