B+Tree索引

B+Tree索引

B树被作为实现索引的数据结构被创造出来，是因为它能够完美的利用“局部性原理”。

什么是局部性原理与磁盘预读？

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

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

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

B树为何适合做索引？

(1)由于是m分叉的，高度能够大大降低；

(2)每个节点可以存储j个记录，如果将节点大小设置为页大小，例如4K，能够充分的利用预读的特性，极大减少磁盘IO；

注意：高度降低的原因在于：

• 在利用了局部性原理前提下，我们把一个节点的大小设为一页，一页4K，假设一个KEY有8byte，一个节点可以存储500个KEY，即j=500
• m叉树，大概m/2<= j <=m，即可以差不多是1000叉树
• 一层树：1个节点，1*500个KEY，大小4K 二层树：1000个节点，1000500=50W个KEY，大小10004K=4M 三层树：10001000个节点，10001000500=5亿个KEY，大小10001000*4K=4G

所以：《高性能Mysql第三版》这本书也说了，一般的B+树都不会超过三层，也就意味着绝大数数据通过三次IO就可以找到

B树，它的特点是：

• 不再是二叉搜索，而是m叉搜索；
• 叶子节点，非叶子节点，都存储数据；
• 中序遍历，可以获得所有节点；

B+树的特点是：

B+树，是在B树的基础上，做了一些改进：

• 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；
• 叶子之间，增加了链表，获取所有节点，不再需要中序遍历；

以上改进让B+树比B树有更优的特性：

• 范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯（范围查询在SQL中用得很多，这是B+树比B树最大的优势）；
• 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；
• 非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引；

索引体现形式

Myisam引擎

使用Myisam引擎的表在数据库中会存在三个文件

以user表为例：

一个是表定义文件 user.frm

一个是索引存储文件 user.MYI

还有一个是数据存储文件 user.MYD

因为Myisam引擎的索引和数据是分开存储的，叫做非聚集索引（UnClustered Index）。并且在B+tree树的叶子节点存储的是数据行的地址，在检索数据时，以此从根节点开始检索，直到找到对应的关键字，然后到数据区获取数据行地址，最后根据这个数据行地址返回检索的数据行