InnoDB底层:B+tree
MyIsAM底层 :Hash
控制查找次数,提高查找效率
实际上,MySQL查询数据的原理:key(索引字段值,可以看B+Tree那里的叶子节点数据)-value(磁盘地址可以看B+Tree那里的节点data)
常见的数据结构有 二叉树、红黑树、B-Tree、B+Tree等,以这几种为例介绍
归根结底其实选择B+tree是因为树的高度小,这样可以查询效率会高,所以应该选择千万级数据但是树高度比较小的数据结构。高度3-4,数据可存储上千万,答案呼之欲出——B+Tree,以下是验证过程。
可视化数据结构 https://www.cs.usfca.edu/~galles/visualization
1、二叉树
概念特点等 查看百度百科 baike.baidu.com/item/%E4%BA…
特点:右大于左
为什么不用:如果二叉树出现只有右子树或者左子树的情况,那么和链表查询无异,效率低下
2、红黑树-二叉平衡树
树的高度有可能很高很高,虽然自平衡但是树的高度不可控,所以不理想
3、B-Tree-多路搜索树
叶子结点具有相同的深度,叶子节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排序
---横向扩展了节点,缩小了高度
更优解——B+tree
4、B+Tree(B-Tree变种)
拥有B-Tree的优点而且:
非叶子结点不存储data,只存储索引(冗余),可以在同一节点放更多索引,进而缩小树的高度
叶子结点包含所有索引字段
叶子结点使用指针连接(B-tree没有哦),提高区间访问的性能
5、InnoDB B+Tree 存放的数据量与树高度的计算
B+tree一个节点==一页==16kb
bigint在mysql中占8byte,mysql(C语言)一个地址占6byte,
所以 一页索引的数据量==16KB/(8+6)B ==1170个==一个节点放的个数
大多数数据库中一行数据1kb撑死了,所以最后放数据的节点个数==16kb/1kb==16个
如果深度为三,那么 1170*1170*16==21902400, 可以存放两千多万个数据
深度为三意味着如果走B+Tree索引的话,三次磁盘IO就能查到;而走全表查询:需要千万级查询...
有些版本的mysql,将索引节点全部放入了内存,效率进一步提升,所以千万级查找大约只需要把数据从节点取出来的时间。
还有个知识点,对比B-Tree可以明白:树的高度由非叶子节点存放的索引数量决定