B树和B+树的区别
·
B树结构如下
B+树结构如下：
两种树的本质都是排好序的数据结构
不同点：
1.B树的叶子节点没有指针，B+树有，有指针可以更加方便范围查询，同一种范围查询，b树可能得多次从头节点开始遍历；
2.b树没有冗余索引，但是b+树有；
3.b树非叶子节点也存放数据，但是b+树只有叶子节点存放数据；
4.存放同样的数据，b树的高度可能比b+树要高。
-------------------------------------------------------------------------------------------------------------
为什么说可能要高呢？
因为mysql的页数据大小系统默认值是16K，结论可看下图sql查询数据。由于b树每个节点都带数据，而b+数只有叶子节点带数据。
以b+树为例，假如带节点的数据为1k，那么叶子节点可以存放16条数据，而第一层和第二层不带数据，索引所占空间大约为8B，下个节点的地址所占空间大约为6B，那么第一层和第二层每个节点大概可以放16*1024/(6+8)=1170个元素，那么3层结构可放的总元为：1170*1170*16=21902400
那么如果b树需要放21902400个元素则需要，16的n次方<21902400，求得n在6到7之间，所以如果用b树结构存储2100万个元素，树的层高为6，查询起来要慢很多。
最后推荐个学习数据结构的网站
数据结构学习网站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)