优点一:B-树降低查询高度,减少磁盘IO读写次数,虽然增加了内存运算,但只要不溢出内存,速率更快.如图一所示,相比于一般的树,B-树高度只有三,查找到节点3/5只要在磁盘上查找三次,但由于节点3/5存储了两个数据,所以增加了内存的运算.
图一
优点二:便是B-树的自平衡.如图二所示,B-树能够自动将各节点数据平衡(图一插入节点4自平衡成图二),这样可以尽可能的放入多的数据仍能保持高度不变(这里还是3),平衡原理大家可以去看一下其他人的文章(个人感觉实现原理较复杂).
图二
B-树主要用于文件系统以及部分数据库索引,比如MongoDB.而Mysql使用B+树作为索引.B+树是B-树的一种变体,有着更高的查询性能.图三所示,B+树每一个父节点的元素都出现在子节点中,是子节点的最大或最小.
图三
子节点包含父节点的所有信息,形成一个有序链表.这样查询速度就会很快了.
图四
B-与B+的卫星数据区别.图五为B-树,不管子节点还是父节点,其数据都是卫星数据(索引元素的数据记录).B+树的叶子节点直接包含微信数据,所以父节点与中间节点都作为索引,指向要查找的卫星数据.这样设计还带来一个好处,B+树的中间节点没有卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素.
图五
图六
B+树对比B-树的优点总结:①.IO次数更少(相同高度可以存储更多);②.查询性能稳定(受高度和内存的影响少);③.范围查询简便(B+树的结构特点).
