WEB开发者-分享WEB开发知识,让开发变得更简单!

深入聊聊mysql索引为什么采用B+树结构

本篇文章是mysql的进阶学习,介绍一下mysql使用B+树作为索引数据结构的原因,希望对大家有所帮助!

深入聊聊mysql索引为什么采用B+树结构

索引提高查询效率,就像我们看的书,想要直接翻到某一章,是不是不用一页一页的翻,只需要看下目录,根据目录找到其所在的页数即可。【相关推荐:mysql视频教程】

在计算机中我们需要一种数据结构来存储这个目录,常见数据结构有哈希表,二叉查找树,二叉平衡树(AVL),红黑树,那为什么Innodb和MyISAM选择b+树呢。

1. 哈希表

哈希表就是一个数组+链表,用下标0,1,2,3..... 表示其数据所在的位置。如果想要在哈希表中存放数据,首先用对这个数据进行散列算法(基本的就是取模运算),假如数组长度是13 ,进行模13之后是0-12,正好对应的数据的下标,如果计算出的下标一样的,就会在下标位置跟上链表。

深入聊聊mysql索引为什么采用B+树结构

缺点:

  1. 利用hash存储需要将所有的数据文件添加到内存,比较消耗内存空间。
  2. hash的查找是等值查询,速度很快,但是各个数据间没有范围规律,但在实际工作中更多的是范围查询,hash就不太合适了。

不能直接说mysql不使用哈希表,而是要根据存储引擎来确定的,Memory存储引擎使用的就是哈希表

2. 二叉查找树

深入聊聊mysql索引为什么采用B+树结构

总结:为什么mysql使用的是B+树

准确的表述:为什么mysql的InnoDB和MyISAM存储引擎的索引使用的是B+树

  • hash表,等值查询是很快的,但是不满足常用的范围查找且相邻的两个值之间没有关系,而且hash比较消耗内存。

  • 二叉树/平衡二叉树/红黑树等都是有且仅有2个分支,共性就是数据量大的时候树的深度变深,增加IO的次数。

  • B树会在节点上存储数据,这样一页存放的key的数量就会减少,增加树的深度。

  • B+树中非叶子节点去除了数据,这样就会增加一页中key的数量,而且叶子节点之间是通过链表相连,有利于范围查找和分页。

原文地址:https://juejin.cn/post/6994810803643744269

作者:纪先生

更多编程相关知识,请访问:编程视频!!

以上就是深入聊聊mysql索引为什么采用B+树结构的详细内容,更多请关注web开发者其它相关文章!

本文链接:https://www.webkfz.com/sjk/sjkzh/1msv.html

版权声明:站内所有文章皆来自网络转载,只供分享作用,不代表本站的观点!

发表评论 共有 0 条评论)

联系客服
网站客服 业务合作 QQ
1244305267
公众号
公众号
公众号
返回顶部