若采用二叉树:

缺点是:若是一个斜二叉树,查询速度和全表扫描没有区别,图如下,所以查询速度由结点的分布决定

若采用平衡二叉树（认为:二路平衡二叉树）

缺点:

太深了:深度决定者io的次数,而io耗时大如若查询8,则需要进行3次io操作

太小了:结点存储的信息太小了，从而导致频繁的io操作

若采用多路平衡二叉树:（B-Tree B树）

路数是结点+1,因为这个是判断逻辑来决定如下图,图一是<1:选择p1,=15:则命中,>15:选择p2,图二会导致>35的无法选择。

一个磁盘块的结点个数:一个磁盘块的大小是16K,若节点存储是int型数据(4个字节)加结点的其他信息(如p1 4个字节),一个磁盘块的结点个数:16*1024/(4+4)=2048个结点,路数是2049路，从而解决了太深了和太小的问题

若采用加强版多路平衡二叉树(B+Tree)

和B-Tree区别:

判断逻辑:B+Tree采用的是闭合区间判断,B-Tree采用开合区间

结点:B+Tree非叶子结点:关键字和子节点的引用,叶子结点:存储数据 B-Tree 非叶子结点和叶子结点存储的是关键字,数据和子节点的引用

顺序:B+Tree叶子结点是顺序的,相邻结点存在顺序引用

为什么选择B+Tree

1  B+Tree拥有B-Tree的优点,深度浅,数据块大

2因为只在叶子结点存储数据,从而导致扫全表的能力强,因为叶子结点是顺序的,从而导致排序功能更强。

3查询时间相对稳定,因为原因1:平衡二叉树,解决了查询不会受到结点分布的影响, 原因2:因为数据在叶子结点,导致每次查询的深度是一样的(相对于B-Tree)

B+Tree索引在mysql中的体现形式

体现形式之一: myisam

体现形式之二: innodb

特点:以主键作为索引,同时也是聚集索引:记录在数据库的顺序和物理地址的顺序是一样的

若以name作为索引,则先用辅助索引找到主键,在根据主键找到对应的数据库记录

两者的区别:

Innodb:通过辅助索引找到主键,在通过主键索引来找到记录,myisam通过索引找到物理地址,再通过物理地址找到对应的记录。

为什么使用索引:

减少存储引擎扫描的数据量如不加索引则先全表扫描在filter筛选,而加索引可以通过数据结构来快速筛选出需要的记录。