树的演变理解

演变过程：

二叉树----》二叉搜索树----->AVL树-----》（多路搜索树）B树------》B+树

 

~~~~~~~~~~~~~~~~~~~~~~~

 

B树就是查找，是值的树，索引是查找值，在B树里找到值后，返回rowid即记录。

rowid是伪列 记录的位置

一个索引一个B树

聚集索引是主键的 只有一个

非聚集索引普通随便 上限可能是200多

 

B树是多路搜索树，为了压缩高度，二叉改为多叉，节点含有更多的关键字

平衡了查找更快 O(lg N) =高度 或 减1

最坏情况 O(N) 

 

 

~~~~~~~~~~~~~~~~~~~~~~~

B树 B+树 AVL树时间复杂度都是lgN，索引还用B树的原因：B树节点关键字多，可以一下查出来整块数据(就算这次用不到以后会用到其它的数据) 减少IO次数，B+树则叶子结点是链表，查询连续的数据更快。

 

 （B树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能）

 

找值时 AVL树是等于找，B树在节点里找到(节点有多关键字)，然后找到再返回该节点，节点含有其它相近的数据，故减少IO次数。OK

 

~~~~~~~~~~~~~~~~

（在数据库中基于范围的查询是非常频繁的，因此MySQL最终选择的索引结构是B+树而不是B树。）

范围查找，数据库多为范围查找：

B+树更快，因为叶子都是链表，只需要找到第一个节点，后面直接链过去，一直到不满足条件为止，

 3--7，顺藤摸过去: B+树

 

B树则是每次都是要遍历整棵树

 （访问完第一个关键字所在的块后，得遍历这个B树，获取下一个块）

 

 

总之，

https://blog.csdn.net/weixin_30531261/article/details/79312676 写道

数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

 也就是说，B树,B+树都减少了IO，但是B+树查起来更快