哈希表, 二叉树，红黑树，B Tree B+Tree B*Tree_哈希表 二叉树 红黑树 b树

目录

一，哈希表

二，二叉树

三，红黑树

四，B树

五，B+树

---

一，哈希表

散列  取模计算，等值查询，范围查询不能用

缺点：

利用hash存储的话需要将所有数据文件添加到内存，比较高飞内存空间；

如果所有的查询都是等值查询，那么hash确实很快，但是实际工作中范围查找的数据更多

二，二叉树

倾斜问题

AVL 二叉平衡树

最长指数和最短指数 不能超过1

旋转，左，右  。旋转浪费时间，插入效率极低，查询很快

三，红黑树

最长指数和最短指数 查不能超过最短的两倍

旋转+变色  减少旋转次数，任何单分支内只能有一个红色。分支的黑色数量相同

是AVL的变种，损失了部分查询性能，提高了插入性能

左旋：逆时针操作，父节点被自己的右孩子取代，而自己成为自己的左孩子

右旋：顺时针操作，父节点被左孩子取代，自己成为自己的右孩子

无论是二叉树还是红黑树，都会因为树的深度过审而造成IO次数变多，影响数据读取的效率

四，B树

1，所有键值分布在整颗树种

2，搜索有可能在非叶子节点结束，在关键字全集内做一次查找，性能逼近二分查找

3，每个节点做多拥有m个子树

4，根节点至少有两个子树

5,分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）

6，所有叶子节点都是在同一层，每个节点最多可以有,-1个key,并且以升序排列

五，B+树

B树的优化，叶子节点直接放置数据。数据量的存储和效率大大提升

B+Tree     文件  ->  偏移量offset  ->  指针  ->  指针移动

B * Tree

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B*树分配新结点的概率比B+树要低，空间使用率更高；