B-Tree (Balance Tree)
假设需要查找data等于5的那条数据，首先找到关键字17和35的数据，发现小于17，于是找到P1的节点，定位到磁盘块2，磁盘块2中的关键字是8和12，5小于8，于是找打p1节点对应的磁盘块5，然后在磁盘块5中找到对应的数据
特性1
- 根节点的子节点个数2 <= x <= m,m是数的阶，假设m=3，则根节点可以有2-3个孩子
- 中间阶段的子节点个数m/2 <= y <= m。假设m=3，中间节点至少有2个孩子，最多3个孩子
特性2
- 每个中间节点包含n个关键字，n=子节点个数-1，且按升序排序。如果中间节点有3个子节点，则里面会有2个关键字，且按升序排序
- Pi(i=1,...n+1)为指向子树根节点的指针。其中P[1]指向关键字小于Key[1]的字数，P[i]指向关键字属于（Key[i-1],Key[i]）的字数，P[n+1]指向关键字大于key[n]的子树。P1、P2、P3为指向字数根节点的指针。P1指向关键字小于Key1的树；P2指向key1-key2之间的子树；P3指向大于Key2的树
B+Tree
- B+Tree是在B-Tree基础上的一种优化
- InnoDB 存储引擎使用B+Tree实现其索引结构
假设需要查找8这条数据，就会首先在磁盘块1中找到5和28这两条数据，8大于5小于28，于是找到P1的节点的对应磁盘块2，然后找到5和10两条数据，8大于5小于10，接着在P1对应的指针中找到对应的数据
B-Tree和B+Tree的差异 1
- B+Tree有n个子节点的节点中含有n个关键字
- B+Tree中，所有的叶子节点中包含了全部关键字的信息，且叶子节点按照关键字的大小自小而大顺序链接，构成一个有序链表
B-Tree和B+Tree的差异 2
- B+Tree中，非叶子节点仅用于索引，不保存数据记录，记录存放在叶子节点中
B-Tree和B+Tree对比
指定查询 where id = 5
对于B-Tree,因为非叶子节点即包含数据，也包含索引，所以时间不固定，最快的情况是，直接在根节点中就能找到数据，最差的情况是在叶子节点才能找到数据。而B+Tree的非叶子节点仅用于索引，所以都是需要找到叶子节点才能找到数据
范围查询 where id between 5 and 10
对于B-Tree,需要先查询5，然后6，一直到10，然后将数据返回。而对于B+Tree，因为叶子节点按照关键字的大小自小而大顺序链接，构成一个有序链表，所以只需要找到5的数据，然后根据链表直接遍历到10即可
InnoDB VS MYISAM
InnoDB存储方式：聚簇索引
- 使用B+Tree
- 主键索引：叶子节点存储主键及数据
- 非主键索引（二级索引，辅助索引）：叶子节点存储索引及主键。即当发送一条数据查询的时候，需要先查询到主键，然后查询到对应的数据。
MYISAM存储方式：非聚簇索引
- 使用B+Tree
- 主键/非主键索引的叶子节点都是存储指向数据块的指针
Hash索引
-
并不是按照索引值排序，所以无法使用排序，
-
不支持部分索引匹配查找如:hash(a,b)-> where a=1
-
只支持等值查询 例如=、IN ,不支持范围查询，模糊查询
-
一般性能比B-Tree(B+Tree)要好一些，hash冲突越严重，性能下降越厉害
B-Tree(B+Tree)特性
可以触发索引的查询：
-
完全匹配：index(name) -> where name = '张三'
-
范围匹配：index(age) -> where age > 5
-
前缀匹配：index(name) -> where name like '张%'
B-Tree(B+Tree)限制
不能触发索引的查询
- 索引为index(name,age,sex)时，查询条件不包括最左列，无法使用索引，如：where age = 5 and sex =1,跳过了索引中的列，也无法完全使用索引，如：where name = '张三' and sex = 1,只能使用name这一列。查询中有某个列的范围查询，则其右边所有列都无法使用索引，如where name = '张三' and age > 20 and sex =1 ,只能使用name、age 两列