B+索引与数据库

context

这一个月忙到爆炸，研究生课程很难，有好多课的作业即使花了很多时间也和别人有很大差距。
peer pressure。感觉别人都是信手拈来，数学算式这么那么就出来我，我就什么都不会。
国内秋招也在我忙作业的过程中要结束了。面试在九月上旬就停了，感觉我的这个项目有点坑，开始上课就要准备毕业找工作，
而且是要在学比较有挑战的课程之间找工作。我太难了。

像西西弗。

问题引入

• 某个sql查询比较慢，为条件字段加索引
• 使用B+数做索引，查询时间log(n)。 hash存索引，查询时间log(1).
• 为什么用B+

content

• 二插排序树，左子树比根小，右子树比根大
• 如果顺序插入，就不平衡了，变成了一边的链表
• 所以要一直保持平衡–>红黑树（TreeSet），保持最小的树高度，提高查找速率

• 想有排序操作的话，比方说每次进一个值都要排序，就用TreeSet

• B树做文件索引比较多，想一下文件列表的层次结构，每个文件夹都有不一定数量的文件，
  文件索引是存在硬盘上的，由于内存大小的原因可能不能一次性加载进来。
  使用B树，每次加载一个节点的数据到内存中。当然每个节点的数据量也不能多，如果都在一个节点，可能还是加载不进来，退化成数组了。
  hashset就是数组存。

• B+数是在B树的基础上改进的，每个数据都在叶子节点上，如图是4路B+树。这里的4路是指有4个子节点。红黑树是2路。

• 数据库中按id查找，可能是查找按id排序的前10名，如果要是用B树，可能就要在一个局部的几个节点中做中序遍历。
  如果用B+树的话，所有数据都是在叶子节点，而且每个叶子节点之间有链表的结构。这样顺序遍历某一块就好了。
• 我觉得B+树结合了链表结构的查找和数组结构的遍历的优点

到这我又想到了跳表，我觉得跳表是在顺序数组的基础上结合和树结构的优势，而B+树是在树结构的基础上结合了顺序存储的优势。
不同的数据库使用不同的结构存储索引