B_Tree

mysql数据文件

id name

1 teacher.MA

2 teacher.ZHOU

3 teacher.ZHANG

4 teacher.LIAN

hash表的索引格式

缺点：

1、利用hash存储的话需要将所有的数据文件添加到内存，比较耗费内存空间

2、如果所有的查询都是等值查询，那么hash确实很快，但是在企业或者实际工作环境中范围查找的数据更多，而不是等值查询，因此hash就不太适合了

二叉树与红黑树

缺点：

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

B树的索引格式

B树特点：

1、所有键值分布在整颗树中

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

3、每个节点最多拥有m个子树

4、根节点至少有2个子树

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

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

实例图说明：

每个节点占用一个磁盘块，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为 16 和 34，P1 指针指向的子树的数据范围为小于 16，P2 指针指向的子树的数据范围为 16~34，P3 指针指向的子树的数据范围为大于 34。

查找关键字28过程：

1、根据根节点找到磁盘块 1，读入内存。【磁盘 I/O 操作第 1 次】

2、比较关键字 28 在区间（16,34），找到磁盘块 1 的指针 P2。

3、根据 P2 指针找到磁盘块 3，读入内存。【磁盘 I/O 操作第 2 次】

4、比较关键字 28 在区间（25,31），找到磁盘块 3 的指针 P2。

5、根据 P2 指针找到磁盘块 8，读入内存。【磁盘 I/O 操作第 3 次】

6、在磁盘块 8 中的关键字列表中找到关键字 28。

缺点：

1、每个节点都有key，同时也包含data，而每个页存储空间是有限的，如果data比较大的话会导致每个节点存储的key数量变小

2、当存储的数据量很大的时候会导致深度较大，增大查询时磁盘io次数，进而影响查询性能