修改表结构字段长度_图解B/B+树看MySQL索引结构

专注于Java领域优质技术号&＃xff0c;欢迎关注

作者&＃xff1a;似水牛年

B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树。

它类似普通的平衡二叉树&＃xff0c;不同的一点是B-树允许每个节点有更多的子节点。

下图是 B-树的简化图&＃xff1a;

B-树

B-树有如下特点:

• 所有键值分布在整颗树中&＃xff1b;
• 任何一个关键字出现且只出现在一个结点中&＃xff1b;
• 搜索有可能在非叶子结点结束&＃xff1b;
• 在关键字全集内做一次查找,性能逼近二分查找&＃xff1b;

B&＃43;树是B-树的变体&＃xff0c;也是一种多路搜索树, 它与 B- 树的不同之处在于&＃xff1a;

• 所有关键字存储在叶子节点出现&＃xff0c;内部节点(非叶子节点)并不存储真正的 data
• 为所有叶子结点增加了一个链指针

简化 B&＃43;树 如下图&＃xff1a;

B&＃43;树

红黑树等数据结构也可以用来实现索引&＃xff0c;但是文件系统及数据库系统普遍采用B-/&＃43;Tree作为索引结构。

MySQL 是基于磁盘的数据库系统,索引往往以索引文件的形式存储的磁盘上&＃xff0c;索引查找过程中就要产生磁盘I/O消耗&＃xff0c;相对于内存存取&＃xff0c;I/O存取的消耗要高几个数量级,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

为什么使用B-/&＃43;Tree&＃xff0c;还跟磁盘存取原理有关。

由于磁盘的存取速度与内存之间效率差异比较大&＃xff0c;为了提高效率&＃xff0c;要尽量减少磁盘I/O&＃xff0c;磁盘往往不是严格按需读取&＃xff0c;而是每次都会预读&＃xff0c;磁盘读取完需要的数据&＃xff0c;会顺序向后读一定长度的数据放入内存。而这样做的理论依据是计算机科学中著名的局部性原理&＃xff1a;

当一个数据被用到时&＃xff0c;其附近的数据也通常会马上被使用&＃xff0c;程序运行期间所需要的数据通常比较集中

由于磁盘顺序读取的效率很高(不需要寻道时间&＃xff0c;只需很少的旋转时间)&＃xff0c;因此对于具有局部性的程序来说&＃xff0c;预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。

MySQL(使用InnoDB引擎),将记录按照页的方式进行管理,每页大小默认为16K(这个值可以修改).linux 默认页大小为4K

使用B&＃43;树的优势

• B&＃43;树更适合外部存储,由于内节点无 data 域,一个结点可以存储更多的内结点,每个节点能索引的范围更大更精确,也意味着 B&＃43;树单次磁盘IO的信息量大于B-树,I/O效率更高。
• Mysql是一种关系型数据库&＃xff0c;区间访问是常见的一种情况&＃xff0c;B&＃43;树叶节点增加的链指针,加强了区间访问性&＃xff0c;可使用在范围区间查询等&＃xff0c;而B-树每个节点 key 和 data 在一起&＃xff0c;则无法区间查找。

MySQL存在多种存储引擎的选择&＃xff0c;不同存储引擎对索引的实现是不同的&＃xff0c;下面对常见存储引擎InnoDB和MyISAM存储引擎的索引实现进行讨论

InnoDB索引实现

使用B&＃43;树作为索引结构&＃xff0c;数据文件本身就是索引文件。数据文件按照B&＃43;树的结构进行组织&＃xff0c;叶节点的data域存储完整的数据记录&＃xff0c;索引的key即为表的主键。

下图为 主键索引 示意图。

InnoDB主索引

可以看到叶节点包含了完整的数据记录&＃xff0c;这种索引叫做聚集索引&＃xff0c;聚集索引使得搜索主键非常高效。

因为InnoDB的数据文件本身要按主键聚集&＃xff0c;所以InnoDB要求表必须有主键(MyISAM可以没有)&＃xff0c;如果没有显式指定&＃xff0c;则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键&＃xff0c;如果不存在这种列&＃xff0c;则MySQL自动为InnoDB表生成一个隐含字段作为主键&＃xff0c;这个字段长度为6个字节&＃xff0c;类型为长整形。

下图为辅助索引示意图&＃xff0c;InnoDB辅助索引的data域存储的是主键的值。搜索辅助索引需要先根据辅助索引获取到主键值&＃xff0c;再根据主键到主索引中获取到对应的数据记录。

InnoDB辅助索引

MyISAM引擎使用B&＃43;Tree作为索引结构&＃xff0c;叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图&＃xff1a;

MyISAM主索引

假设我们以Col1为主键&＃xff0c;可以看出MyISAM的索引文件仅仅保存数据记录的地址。

在MyISAM中&＃xff0c;主索引和辅助索引(Secondary key)在结构上没有任何区别&＃xff0c;只是主索引要求key是唯一的&＃xff0c;而辅助索引的key可以重复。

如果我们在Col2上建立一个辅助索引&＃xff0c;则此索引的结构如下图所示&＃xff1a;

MyISAM辅助索引

链接&＃xff1a;https://www.jianshu.com/p/9bd572b0a0d4