【学习笔记】mysql索引原理之B+/-Tree

  1. 云栖社区>
  2. 博客>
  3. 正文

【学习笔记】mysql索引原理之B+/-Tree

般若灵芝 2018-10-18 10:51:02 浏览661
展开阅读全文

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

1、B-Tree

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

2、B+Tree

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

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

3、读内存和读磁盘

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

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

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

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

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

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

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

为了尽量减少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查询时,效率极高,直接按位与/或就可以得到结果了。所以,应用范围局限。

网友评论

登录后评论
0/500
评论
般若灵芝
+ 关注