浅谈数据库的索引

我们知道,数据库的分类有关系型数据库和非关系型数据库。关系型数据库的代表是MySQL。这里我们不谈关系型和非关系型的区别于联系,只侧重于讲讲关系型数据库的索引实现原理。

之所以称为关系型数据库,是因为它记录了各种数据之间的“关系”,我们可以形象地将若干个属性它看做一张表,一个数据库有若干个这样的表,这些表之间靠某些共有的字段连接起来,就构成了他们之间的关系。

试想,我们在进行表查询的时候,一般都需要扫描整张表,即全表扫描。而这些数据都是存储在磁盘上的,不用我说,磁盘I/O都是很慢的,大概是内存I/O的10000倍左右。这就导致数据库的查询操作效率很低,而究其原因,就是因为我们查询了很多不必要的数据属性。而改进办法很简单,就是尽力减少磁盘I/O。

此时就出现了索引的概念。索引就是对表中某个(些)字段进行排序的数据结构,一般采用B+树实现,每次查询操作最快只需要O(lgN)的时间复杂度。具体原因请看:

所谓B+树,是专为减少磁盘I/O而生的。一棵4阶的B+树示意图如下:

可以看出,在B+树中,所有数据均保存在叶子节点上,并且叶子节点是排序的,并且各叶子节点之间用指针连接起来。这样在B+树中查找数据时,只需要根据路径上的索引找到对应的叶子节点,然后利用二分查找再找到对应的值即可。

B+树实现索引的好处是,每次查找时不必执行全表扫描,也就是不必将磁盘上的所有数据都加载进内存,只需要加载对应的叶子节点到内存即可。所以对任何单个数据的查询,都只需要进行一次磁盘I/O即可。

使用B+树的另一个好处是,B+树的所有叶子节点都用指针连接起来了。所以要查找某一区间内所有的数据时,可以先从根节点找到区间的下界节点,此操作的时间复杂度为O(lgN),然后再利用叶节点的指针遍历,直到找到区间上界节点为止,设区间的长度为M,此操作的时间复杂度为O(M),所以总共的时间复杂度为O(M+lgN)。这是非常高效的。

综上,使用B+树可以极大提高磁盘查找的效率。当然,索引不只可以使用B+树,B树,位图都可以作为索引使用的数据结构,这里不再赘述。

【完】