索引

• 需要解决的问题：精确查询和范围查询。
• 要求：查询性能高和存储空间不要太大。

尝试

• 哈希表，精确查询可以，范围查询不行
• 平衡二叉查找树，同样，精确查询可以，但是范围查询有困难。
• 跳表：就是把链表的节点数变少，索引只表示该区间起始值。
  

二叉查找树到B+树

• 非叶子节点不再存储数据，将数据放到叶子节点中，把叶子节点串在一条链表上。
  
• 改造后，求区间的数据只需要拿区间的起始值，在树中进行查找，当查到叶子节点后，顺着链表往后便利，直到链表中的节点数据大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。
• 但是如果为大量数据构建索引，索引要是放在内存中，虽然快，但是占用空间会很大。
• 如果放在硬盘里，数据查找时从磁盘中读取，但是这样速度又会下降。每个节点的访问都相当于一次磁盘IO。树的高度就等于每次查询要做的磁盘IO次数（因为数据在叶子节点）。
• 所以现在就要想办法把树高度降低，如何降低呢，那就是把二叉树变成多叉树。
• 那到底变成多少叉合适呢，首先明确，不管磁盘中的数据还是内存中的数据，操作系统都是按页存储，即一次读一页（通常大小是4KB），在选择多少叉时，要尽量让每个节点大小等于一页的大小。
• B+树这个多少叉（设为m）是根据页的大小事先计算的，即一个节点最多m个子节点，在写入时，可能会让索引中某些节点的子节点数超过m，这个节点大小就超过了一个页，读这样的节点就需要多次磁盘IO。
• 为了解决这个问题，需要将节点分裂。如果父节点因此也超过了m（因为现有子节点比原先多了），需要再分裂，直到根节点。
• 删除时，若一个节点的子节点个数小于m/2，则可以将子节点合并。

B+树特点

• 每个节点中子节点个数不超过m，不小于m/2。
• 根节点的子节点个数可以不超过m/2。
• 一个节点存储一页数据，由此来定m，树只存储索引，数据在叶子节点。
• 通过链表将叶子节点连接，方便范围查找。
• 一般情况，根节点在内存中，其他节点在硬盘中。

B树

• B树中非叶子节点也存数据，叶子节点不需要链表串联。