Home > Database > Mysql Tutorial > mysql索引原理之B+/-Tree

mysql索引原理之B+/-Tree

WBOY
Release: 2016-06-07 16:37:31
Original
1308 people have browsed it

http://hi.baidu.com/lzpsky/item/70b944dffe4a9e16e1f46f27 索引,是为了更快的查询数据,查询算法有很多,对应的数据结构也不少,数据库常用的索引数据结构一般为B+Tree。 1、B-Tree 关于B-Tree的官方定义个人觉得比较难懂,通俗一点就是举个例子。假如:

http://hi.baidu.com/lzpsky/item/70b944dffe4a9e16e1f46f27


索引,是为了更快的查询数据,查询算法有很多,对应的数据结构也不少,数据库常用的索引数据结构一般为B+Tree。

1、B-Tree

关于B-Tree的官方定义个人觉得比较难懂,通俗一点就是举个例子。假如:一本英文字典,单词+详细解释组成了一条记录,现在需要索引单词,那么以单词为key,单词+详细解释为data,B-Tree就是以一个二元组{key,data}来定义一条记录。如果一个节点有3条记录,那么会有对应的4个指针,用以指向下一个节点。B-Tree是有序且平衡的,所有叶子节点在同一层,即不会出现某个分支层级多,某个分支层级少的情况。

因为B-Tree是有序的,所以它的查找就简单了,先从根节点开始二分查找,找到则返回节点;否则沿着区间指针查找下一个节点。比如,查询false这个单词。

2、B+Tree

与B-Tree不同的是,B+Tree每个节点只有key,没有data;而且叶子节点没有指针。也就是说B+Tree的叶子节点和内节点的数据结构是不一样的。


一般数据库采用的是B+Tree,而且经过了一些优化,比如在叶子节点上增加了顺序访问指针,提高区间查询效率。比如:查询首字母为f~t的所有单词。那么只需查到f开头的第一个单词fabric,然后沿着叶子节点的开始遍历,直到找到最后一个以t开头的单词为止。


?

简单介绍了B-/+Tree,至于众多数据结构中,为何数据库索引选择BTree,而且选择B+Tree,下面从计算机存储原理方面简单说说。

3、读内存和读磁盘

内存读取和磁盘读取的效率是相差很大的。

简单点说说内存读取,内存是由一系列的存储单元组成的,每个存储单元存储固定大小的数据,且有一个唯一地址。

当需要读内存时,将地址信号放到地址总线上传给内存,内存解析信号并定位到存储单元,然后把该存储单元上的数据放到数据总线上,回传。

写内存时,系统将要写入的数据和单元地址分别放到数据总线和地址总线上,内存读取两个总线的内容,做相应的写操作。

内存存取效率,跟次数有关,先读取A数据还是后读取A数据不会影响存取效率。而磁盘存取就不一样了,磁盘I/O涉及机械操作。

磁盘是由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘须同时转动)。磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不动,磁盘转动,但磁臂可以前后动,用于读取不同磁道上的数据。磁道就是以盘片为中心划分出来的一系列同心环(如图标红那圈)。磁道又划分为一个个小段,叫扇区,是磁盘的最小存储单元。


磁盘读取时,系统将数据逻辑地址传给磁盘,磁盘的控制电路会解析出物理地址,即哪个磁道哪个扇区。于是磁头需要前后移动到对应的磁道,消耗的时间叫寻道时间,然后磁盘旋转将对应的扇区转到磁头下,消耗的时间叫旋转时间。所以,适当的操作顺序和数据存放可以减少寻道时间和旋转时间。

为了尽量减少I/O操作,磁盘读取每次都会预读,大小通常为页的整数倍。即使只需要读取一个字节,磁盘也会读取一页的数据(通常为4K)放入内存,内存与磁盘以页为单位交换数据。因为局部性原理认为,通常一个数据被用到,其附近的数据也会立马被用到。

4、检索性能分析

B-Tree:如果一次检索需要访问4个节点,数据库系统设计者利用磁盘预读原理,把节点的大小设计为一个页,那读取一个节点只需要一次I/O操作,完成这次检索操作,最多需要3次I/O(根节点常驻内存)。数据记录越小,每个节点存放的数据就越多,树的高度也就越小,I/O操作就少了,检索效率也就上去了。

B+Tree:内节点只存key,大大滴减少了内节点的大小,那么每个节点就可以存放更多的记录,树的更矮了,I/O操作更少了。所以B+Tree拥有更好的性能。

5、其他索引方式

散列索引:通过HASH来定位的一种索引,这种索引用的较少,通过用于单值查询。InnoDB的自适应索引就是HASH索引。

位图索引:字段值固定且少,比如性别、状态。在同时对多个这样的字段and/or查询时,效率极高,直接按位与/或就可以得到结果了。所以,应用范围局限。

作者:javaACMer 发表于2013-6-5 23:12:40 原文链接

阅读:79 评论:0 查看评论

mysql索引原理之B+/-Tree

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template