浅析B树与B+树-一一网

这是我参与更文挑战的第8天，活动详情查看：更文挑战

最近在看mysql的一些书时，脑海中闪过一个年头，B+树这里我知道了，B树我也大概了解，那他两是啥，哦豁，忘了，所以有时还是有必要总结一波

写树之前思考一个问题，在开发过程中我们最常用的查找数据，是不是hashmap，老生常谈了，那有没有想过为什么抛弃了hash算法而选择了树呢？而且Memory引擎现在还支持hash呢！问题留到最后回答。。。

B树

B树（Balance-tree）即B-tree即B-树，==>B树=B-树，由于翻译问题，会让初学者产生误解，记住啊，B树就是B-树，

太多的概念这里就不说了，网上一大堆，主要说一些我的认知范围内个人认为需要注意的重点，B树也叫多路平衡查找树，不同于二叉树的是它的子节点不是两个，而是多个，，相信大家都知道页的概念，他是我们数据存储的基本单位，

这是我从百度上找的一个图，其实这张图不能表达我的意思，因为它把每个节点上的数据没写，B树的每个节点都存储数据的，所以每页上面能存储的数据量就少了，而我们要查找数据就必须进行比对，向下面节点查找如果没查到就必须回到根节点继续向下查找，如此反复直到查到，而每次来回跑根节点需要不停IO，而且页数据少，也要不停的IO查页数据，大部分时间都用在跑路上了，真正查找的时间却没有多少；

B+树

说完了B树的缺点，那么B+树当然就要优化这些缺点了，首先对于页存储结点数据过少的情况，将所有的数据都放到了叶子上了，中间的结点全部存放索引值，这样可以最大化的存放关键字，对于需要不停地查找结点，一次没查到需要返回到根节点处继续往下遍历，B+树便让每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依关键字的大小自小而大顺序链接

百度上的这个图就很有意思，很好的表达了我的想法每一层都用双向链表连接各自的页，在页目录里不论是B树还是B+树用的都是二分法，因为他们的数据都是顺序排列的，所以不用担心为什么用二分法，这里不禁就有人思考了，那我不用这个主键索引怎么办，我又建了个二级索引，这里得说明，如果你有自己创建的索引，它会根据你新建的索引来再生成一颗小树树，下次可以的话就从小树树这里查，所以，这也正是别人说的索引不是越多越好，多了，修改数据需要维护的树就多了，另外，记住，注意防止回表查询呦，，，