Mysql数据库索引原理--数据结构及算法基础

**

数据结构及算法基础

**

索引（Index）是帮助数据库高效获取数据的数据结构。

索引的本质：索引是一种数据结构。

由于数据库数据本身的组织结构不可能完全满足各种优化排序算法的数据结构要求（二分查找、二叉树查找等）。所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。

B-Tree和B+Tree

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

B-Tree

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

（1）d>=2，即B-Tree的度；每个非叶子节点至少包含两个子节点

（2）h为B-Tree的高；

（3）每个非叶子结点由n-1个key和n个指针组成，其中dnode);

}

return BTree_Search(point[i+1]->node);

}

data = BTree_Search(root, my_key);

例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找结点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

B+Tree

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

（1）每个结点的指针上限为2d而不是2d+1。

（2）内结点不存储data，只存储key；

（3）叶子结点不存储指针。

图3是一个简单的B+Tree示意。

图3

由于并不是所有节点都具有相同的域（存储空间），因此B+Tree中叶结点和内结点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个结点的域和上限是一致的，所以在实现中B-Tree往往对每个结点申请同等大小的空间。

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

图4

如图4所示，在B+Tree的每个叶子结点增加一个指向相邻叶子结点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着结点和指针顺序遍历就可以一次性访问到所有数据结点，极大提到了区间查询效率。

为什么使用B-Tree（B+Tree）

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

B-/+Tree索引的性能分析

从使用磁盘I/O次数评价索引结构的优劣性：根据B-Tree的定义，可知检索一次最多需要访问h个结点。数据库系统的设计者巧妙的利用了磁盘预读原理，将一个结点的大小设为等于一个页面，这样每个结点只需要一次I/O就可以完全载入。

为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建结点时，直接申请一个页面的空间，这样可以保证一个结点的大小等于一个页面，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

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

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

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

B+Tree更适合外存索引，是和内结点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于结点内key和data的大小：dmax=floor(pagesize/(keysize+datasize+pointsize))。

floor表示向下取整。由于B+Tree内结点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!