二叉查找树

原理略

当查找节点9时，由于是对半查找，所以此时的时间复杂度为O(logn)，且需要进行三次的IO读写

当删除节点2和节点6，并添加节点11和节点13时，此时二叉查找树会变成如下，此时查找节点13的时间复杂度为O(n)，且需要进行五次的磁盘IO才能找到节点

二叉查找树的缺陷：
1、经过频繁的修改操作之后，二叉树会变成一条，从而使时间复杂度变为O(n)，也大大增加了磁盘IO的次数。
2、即使是平衡二叉树，二叉查找树的层级过多，虽然时间复杂度为O(logn)，但磁盘的IO次数过多，效率低下。

B树

定义一：

1. 孩子节点的个数
2. 叶子节点必须位于同一层

定义二：

1. 关键词必须比孩子节点少一个
2. 关键词的大小排序

相比较平衡二叉树：

1. 查询的时间复杂度与平衡二叉树相同，都是O(logn)
2. 由于存储的关键字更多，存储的内容比平衡二叉树更多
3. 孩子节点更多，层级更少，磁盘IO次数更少

B+树

相比于B树，B+树的区别

注意：P[i]>=k[i]不是硬性要求

相比于B树的优点：
1、由于数据都存储在叶子节点中，所以内部节点的个数会减少，树的层级会降低，减少IO次数，磁盘读写代价更低。
2、由于内部节点没有指向数据，只是索引，所以任何关键字的查找的路径长度相同，所以B+树的查询时间相同，稳定为O(logn)，查询的效率更稳定。
3、由于在叶子节点中添加了链表且B+树的索引按大小顺序排列，如，当查询大于或小于操作时，可以直接通过链表进行范围查询即可。使得B+树更利于对数据库的扫描。

Hash

hash索引在同hash值的情况较少时，比B+树的效率更高