B+树索引和Hash索引

B+树索引

B+树的一些优点和特性

1. B+树是一棵平衡树，每个叶子节点到根节点的路径长度相同，查找效率较高；
2. B+树的所有==关键字都在叶子节点==上，因此范围查询时只需要遍历一遍叶子节点即可；
3. B+树的叶子节点都按照关键字大小==顺序存放==，因此可以快速地支持按照关键字大小进行排序；
4. B+树的非叶子节点不存储实际数据，因此可以存储更多的索引数据；
5. B+树的非叶子节点使用指针连接子节点，因此可以快速地支持范围查询和倒序查询。
6. B+树的叶子节点之间通过==双向链表链接，方便进行范围查询==。、

因此我们使用 B+树实现索引，就有以下优点

1. 支持范围查询，B+树在进行范围查找时，只需要从根节点一直遍历到叶子节点，因为数据都存储在叶子节点上，而且叶子节点之间有指针连接，可以很方便地进行范围查找。
2. 支持排序，B+树的叶子节点按照关键字顺序存储，可以快速支持排序操作，提高排序效率；
3. 存储更多的索引数据，因为它的非叶子节点只存储索引关键字，不存储实际数据，因此可以存储更多的索引数据；
4. 在节点分裂和合并时，IO操作少。B+树的叶子节点的大小是固定的，而且节点的大小一般都会设置为一页的大小，这就使得节点分裂和合并时，IO操作很少，只需读取和写入一页。
5. 有利于磁盘预读。由于B+树的节点大小是固定的，因此可以很好地利用磁盘预读特性，一次性读取多个节点到内存中，这样可以减少IO操作次数，提高查询效率。
6. 有利于缓存。B+树的非叶子节点只存储指向子节点的指针，而不存储数据，这样可以使得缓存能够容纳更多的索引数据，从而提高缓存的命中率，加快查询速度。