B+TREE、聚簇、非聚簇

1、BTREE实现原理

(1)原理图如下:

(2)特点:
每个节点占用一个盘块的磁盘空间,一个节点上有两个升序排序的关键字和三个指向子树根节点的指针,指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
(3)查找过程:
以根节点为例,关键字为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35,模拟查找关键字29的过程:

  • 根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】
  • 比较关键字29在区间(17,35),找到磁盘块1的指针P2。
  • 根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】
  • 比较关键字29在区间(26,30),找到磁盘块3的指针P2。
  • 根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】
  • 在磁盘块8中的关键字列表中找到关键字29。

分析上面过程,发现需要3次磁盘I/O操作,和3次内存查找操作。由于内存中的关键字是一个有序表结构,可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数,使每次磁盘I/O取到内存的数据都发挥了作用,从而提高了查询效率。

2、B+TREE实现原理

(1)原理图如下:

(2)特点:

  • 非叶子节点只存储键值信息
  • 所有叶子节点之间都有一个链指针
  • 叶子节点也多存储了指向下一个叶子节点的指针,更方便叶子节点的范围遍历
  • 数据记录都存放在叶子节点中

3、MyISAM-非聚簇索引

MyISAM中, 主索引和次索引,都指向物理行(磁盘位置),称为非聚簇索引。
(1)原理图如下:

(2)特点:

  • 索引文件和数据文件是分离的
  • 索引文件仅保存数据行记录的地址(行指针)
  • 主索引与二级索引无区别
  • 二级索引也存储的是行指针

4、InnoDB-聚簇索引

InnoDB的主索引文件上直接存放该行数据,称为聚簇索引,次索引指向对主键的引用。
(1)原理图如下:

(2)特点:

  • 主键索引既存储索引值,又在叶子节点中存储整行的数据
  • 二级索引存储索引列值+主键信息
  • 如果没有主键, 则会Unique key做主键
  • 如果没有unique,则系统生成一个内部的rowid做主键

5、MyISAM和InnoDB的二级索引的对比


(1)InnoDB二级索引的叶子节点存放的是KEY字段+主键值,因此首先通过二级索引查找到的是主键值,再根据主键值在朱建索引中查找到相应的数据文件。
(2)MyISAM的二级索引存放的还是列值和行号的组合 叶子节点中保存的是指向物理数据的指针,因此它的主建索引和二级索引的结构并没有任何区别,只是说主键索引的索引值是唯一且非空的,而MyISAM引擎可以不设置主键。
(3)InnoDB引擎是必须设置主键的,需要依赖主键生成聚簇索引,因此当没有指定主键的时候,InnoDB引擎会默认寻找一个可以唯一标识每行数据的列作为主键,当这种列不存在的时候,会默认生成一个6字节整型的隐藏列作为主键。