B-Tree 简介
BTree 是一种多路搜索树
- 定义任意非叶子节点最多只有M个儿子 ， M> 2
- 根节点的儿子数为 [2,M]
- 除根节点外的非叶子节点的儿子数为 [M/2,M]
- 每个节点存放至少 M/2-1 (向上取整) 和 至多M-1 个关键字 (至少2个关键字)
- 非叶子节点的关键字个数 = 指向儿子的指针个数 -1
- 非叶子节点的关键字： K[1]、K[2] ...K[M-1] , 且 K[i] < K[i+1]
- 非叶子节点的指针：P[1]、P[2] ...P[M] ，其中 P[1] 指向关键字小于 K[1] 的子树，P[M] 指向关键字大于 K[M-1] 的子树
- 所有叶子节点位于同一层
特点：
- 关键字集合分布在整棵树中
- 任何一个关键字出现且只出现在一个节点中
- 搜索有可能在非叶子节点结束
- 其搜索性能等价于关键字全集内做一次二分查找
- 自动层次控制
B-Tree 的搜索，从根节点开始，对节点内的关键字(有序)进行二分查找，如果命中则结束，否则进入查询关键字范围的儿子节点。重复直到对应的儿子指针为空，或者已经是叶子节点
B+Tree
B+Tree 是 B-Tree 的变体，也是一种多路搜索树
- 非叶子节点的子树指针与关键字个数相同
- 非叶子节点的子树指针 p[i] ，指向关键字值属于 (K[i] ,K[i+1]) 的子树
- 所有的叶子节点增加一个链指针
- 所有关键字都在叶子节点出现
特点：
- 所有关键字都出现在叶子节点的链表，且链表中的关键字恰好是有序的
- 不可能在非叶子节点命中
- 非叶子节点相当于叶子节点的索引，叶子节点相当于是存储关键字数据的数据层
- 更适合文件索引系统
B+Tree因为非叶子节点不存放数据，所以相对于B-Tree可以存放更多的键与指针，让树变得更矮，这样降低了I/O操作
不同的存储引擎对索引有不同的支持：Innodb 和 MyISAM 默认的索引是Btree ， 而 memory 默认的索引是 Hash 索引
聚簇索引
聚簇索引就是指主索引文件和数据文件为同一份文件，聚簇索引主要用在Innodb 存储引擎中。在该索引实现方式中 B+Tree 的叶子节点上的 data 就是数据本身，key 为主键。如果是一般索引的话，data 便会指向对应的主索引
在B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的 B+Tree ，这样做的目的是为了提高区间访问的性能
非聚簇索引
非聚簇索引就是指B+Tree的叶子节点上的data ,并不是数据本身，而是数据存放的地址。主索引和辅助索引没有区别，只要主索引中的 key 一定得是唯一的，主要用在 MyISAM 存储引擎中。
非聚簇索引比聚簇索引多了一次读取数据的IO 操作，所以查找的性能会差
哈希索引
哈西算法的时间复杂度为O(1) ，哈希表也称为散列表，在哈希的方式下，一个元素 k 处于 h(k) 中，即利用哈希数 h ,根据关键字 k 计算出槽的位置，函数 h 将关键字映射到哈希表 T[0 ...m-1] 的槽位上
上图中哈希函数 h 可能将两个不同的关键字映射到相同的位置，这叫碰撞，在数据库中一般采用链接法解决，在链接法中，将散列到同一个槽位的元素放在一个链表中，如下图
BTree