`
dwj147258
  • 浏览: 194680 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

索引的底层结构

阅读更多

根据前两篇的铺垫,今天我们可以去具体看看索引的知识了。索引的知识以mysql为基本,虽然本人项目使用的PGSql....

B,B+树的性能考量:

我们知道数据库的文件都是存储在磁盘中,那么IO操作就是评价一个索引结构好坏的最好标准。如果这个索引是顺序结构,那么查询一个数据的时间复杂度就是O(N),数据少还行,到百万,千万级别的时候,查询一次也要O(N),就意味着N次IO,要命。

而B树则不然,根据第一章的学习,访问B树中最下方的一个节点数据,只发生了3次IO操作(查找了3个高度的节点,最终定位到当前节点中)。而更巧妙的地方在于,数据库系统在设计的时候,一个节点的大小就等于一页的大小(关于页的概念,此文不分析),这就意味着一次IO就能一个节点完全载入其中。

1.B树的时间复杂度是一个渐进式的O(h)=O(log d(N) )。h是树高,d是度,也就是分支的数目,N是总记录数。

2.B树的高度 h=log(m+1)N(不确定,但是估计关系差不多是如此),假设 数据总量是N,每个节点的数据项是m。由此可知N一定的情况下,m越大,h就越小。而m = 节点的大小/数据项的大小。而节点的大小刚刚说过,大小基本就是确定的,因此如果数据项空间越小,则m就越多,m越多,树的高度h就越小,查找更有利。

这也就是索引字段为什么要小的缘故,小了的话节点的数据项就越多,高度就越小。而B+树内把真是的数据又放在了叶子节点中,非叶子节点中只存放了索引的数据,保证了数据项尽可能的多。保证树的高度。

Mysql中存储引擎的索引实现:

Mysql有两种存储引擎,MyISAM和InnoDB,InnoDB常听说,好像用的也是最多的,MyISAM不常听说。

1.MyISAM使用的是B+树作为引擎,下图展示的是主键索引的示意图:

可以看见索引文件和数据记录其实是分开来的,索引文件里存储的其实是数据记录的地址。

2.MyISAM辅助索引和主键索引类似,但是辅助索引的key可以重复,这是和主键不同的地方。

3.InnoDB的索引实现也是B+树,但是具体的方式确不一样。

3.1第一点,数据文件本身就是索引文件,这一点怎么理解呢?还记得B+树的叶子节点存储了具体数据嘛,在InnoDB里,叶子节点存储的树真正的数据值,而不是MyISAM里存储的是地址。索引的key就是数据表的主键。InnoDB主索引的示意图如下,可以看见叶节点包含了完整的数据记录,这种索引也叫做聚集索引。因为InnoDB的数据文件本身要按照主键聚集,所以必须要有主键。如果没有显示指定,则Mysql会自动选择可以唯一标识的数据列作为主键,如果不存在这种列,则Mysql自动为InnoDB生成一个隐含字段,占位6字节,长整型。

3.2InnoDB辅助索引也和MyISAM不同,辅助索引里面存储的是数据的主键而不是地址,可以这么说InnoDB的辅助索引最终还是要依赖主键索引来实现。下图是以名字为索引的单列索引B+树结构:

3.3辅助索引里面有一个比较特殊的索引叫覆盖索引。它奇特在哪边呢?从3.2我们知道辅助索引的data区域其实存储的是主键的地址,需要通过主键进行再一次定位访问到具体的数据。那么假设:

select uage,uname from user where uage = 12; 

如果我们建立的是复合索引(uage,uname)的话,上面一条语句会用到索引,而且能够直接返回出ucard和uname,而不需要再去进行主键定位的操作,这就是特别之处。所以这个复合索引其实可以说成是一种覆盖索引。

那么复合索引的B+树结构是怎么样的呢?这里我们假设user表结构中的联合索引是(age,name,address)。下图不能确认是否是正确的,只是通过参考不同的文章总结出的自己的假设。

通过这个结构我们可以看见,在叶子节点中存储的数据是age,name,address的值(假设这些数据都是按照顺序排列好的,图中是随意写的),那么如果我们只想要这几个值的话,都不需要再进行主键定位查询了,提高了一些效率。

小结:

InnoDB的聚集索引是按照主键搜索,是最高效的,辅助索引需要走两次索引,首先查询辅助索引得到主键,再跟进主键查询获得记录。

问题1:不建议主键字段过长:原因上面第2点也讲过一些,过长会造成数据项空间变大,每个节点数据项数目变少,高度增加。

另外我们发现辅助索引的data域记录的也是主键,因此简介造成辅助索引变大,查询困难。

问题2:非单调字段:如果不是单调字段的话,会造成B+树不断的调整,十分低效,上一篇分析过插入和删除。使用自增字段的话会保持一个相对稳定的顺序。
---------------------
作者:刘二郎
来源:CSDN
原文:https://blog.csdn.net/qq_32924343/article/details/80199977
版权声明:本文为博主原创文章,转载请附上博文链接!

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics