索引的作用是提高查询效率,其实现方式有很多种,常见的索引模型有哈希表、有序列表、搜索树等。 哈希表 一种以key-value键值对的方式存储数据的结构,通过指定的key可以找到对应的value。 哈希把值放在数组里,用一个哈
索引的作用是提高查询效率,其实现方式有很多种,常见的索引模型有哈希表、有序列表、搜索树等。
1.二叉树:
2.B树(多叉树):
3.B+树:
因为索引不止存在内存中,还要写在磁盘上,为了尽量少地读写磁盘,减少io次数,所以尽管二叉树的效率很高,大多数数据库不会选择二叉树。
可以想象一下一棵 100 万节点的平衡二叉树,树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说,对于一个 100 万行的表,如果使用二叉树来存储,单独访问一个行可能需要 20 个 10 ms 的时间。
InnoDB使用B+树索引模型,所有数据都存储在B+树中,每一个索引对应一棵B+树。
以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。这棵树高是 4 的时候,就可以存 1200 的 3 次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。
InnoDB采用B+树结构,是因为B+树能够很好地配合磁盘的读写特性,减少单次查询的磁盘访问次数,降低IO、提升性能。
--结束END--
本文标题: MySQL-InnoDB为什么采用B+树结构实现索引
本文链接: https://www.lsjlt.com/news/5826.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-26
2024-04-26
2024-04-26
2024-04-26
2024-04-26
2024-04-26
2024-04-24
2024-04-24
2024-04-24
2024-04-24
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0