索引数据结构探索
数据库的索引，主要是为了降低查询的时间复杂度，遍历查询n行，比较元素的时间复杂度为O(N)。如果把查找数据变成二叉树的结构，至顶而下，比较元素的复杂度为O(logN)。速度提高了一个水平。但是由于数据量的庞大，索引的数据量非常大，直接存在内存是不太可能的了，从硬盘读取索引文件，读取的次数成为慢的主要原因。如果把二叉树压缩成一个矮胖矮胖的树结构，那么磁盘读取的次数就减少了。
b树的特征
m阶的b树，特征如下：
- 根结点至少有两个子女。
- 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
- 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
- 所有的叶子结点都位于同一层。
- 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
b+树的特征
- 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
- 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
b+树相对于b树的优点
- IO次数少，因为中间节点不存数据，只存索引，能存更多的索引
- 查找稳定，数据都在叶子节点上
- 查找范围数据时更方便，因为B+树叶子节点的数据从小到大排列了。而b树需要从最小值遍历到最大值。
数据库索引分类
- 聚集索引
数据行的物理顺序与索引值得逻辑顺序相同，一个表只能拥有一个聚集索引。 - 非聚集索引
非聚集索引的叶子节点依然是索引。数据行的物理顺序与索引值的逻辑顺序不相同。一个表能拥有多个聚集索引。 - 复合索引
解决非聚合索引的二次查询问题（通过聚合索引才能查到物理地址），复合索引的列包含要查询的列。要满足最左侧索引的原则。
