MySQL索引

1

P1

data

K21

K48

杭州

4

5

P3

磁盘块6

K：键值，即表中记录的主键

3

K25

绍兴

西安

2

数据库记录

6

data：数据，即除主键之外的数据

磁盘块8

P2

K50

磁盘块1

K23

K38

磁盘块3

南阳

K52

B树的缺点：1、每个节点都有Key，同时每个Key都会对应有数据区域data，而每个页存储空间是有限的，如果data数据占用内存较大，会导致每个节点存储Key数量减少2、当存储数量很大，会导致深度较大，增大查询时磁盘I/O的此时，从而影响性能

0X0059

id

郑州

K8

磁盘块5

K66

K5

K18

K2

0X0023

K22

K56

K32

K12

B+树

0X0018

MySQL中InnoDB和MyISAM中的B+树

图例说明：1、每个接点占据一个磁盘，一个节点上有两个生升序排序的关键字K和三个指向子树节点的指针P，指针P存储子节点所在磁盘块的地址2、两个关键字K划分成三个范围域对应撒个指针指向子树的数据范围以根节点（所在磁盘块1）为例，关键字为25和50，P1指向数据范围小于25的子树，P2指向数据范围在25和50之间的子树，P3指向数据范围大于50的子树，

K51

K30

city

磁盘块7

K53

咸阳

磁盘块2

查找关键字的过程：1、根据根节点查找磁盘块1，读入到内存（第1次磁盘I/O）2、比较关键字K32在（K25，K50）区间，找到磁盘块1的P2指针3、根据磁盘块1的P2指针找到磁盘块3，读入内存（第2次磁盘I/O）4、继续比较K32，锁定在（K30，K38）区间，找到磁盘块3的P2指针5、根据磁盘块3的P2指针锁定磁盘块8，读入内存（第3次磁盘I/O）6、在磁盘块6中的关键字列表中找到关键字K32注意：再次过程中，进行了3次磁盘I/O

注意：在B+树上有两个头指针，一个指向根节点，一个指向关键字最小的叶子节点，而且所有的叶子结点（即数据节点）之间是链式环结构。          因此可以对B+树进行两种查找运算：1、对于主键的范围查找和分页查找，2、从根节点开始进行随机查找同时相比于B树，同样是需要进行3次I/O，但是B+树存储数据量更大

B树的特点1、所有键值分布在整颗树中2、搜索有可能排在非叶子节点结束，在关键字全集内做一次查找，性能接近二分查找3、每个节点最多拥有m个子树，根节点至少有2个子树，分支节点至少拥有m/2个子树（除根节点和叶子节点都是分支节点）4、所有叶子结点都在同一层，每个节点最多可以有m-1个key，并且按照升序排列

磁盘块4

K33

磁盘块9

B树

0X0027

InnoDB中的B+树

P：指针，即存储子节点的地址

磁盘块10

K24

MyISAM中的B+树

B+树是在BTree的基础之上进行变化的，其特点为1、B+ 树每个节点可以包含更多的节点，这样可以在同样的数据量基础上，降低树的高度，同时将数据范围变为多个区间，区间越多，数据检索越快2、非叶子结点只存储key，叶子结点存储key和数据data3、叶子节点两两指针相互链接（符合磁盘的预读特性），顺序查询性能更高

根据图可知：InnoDB叶子节点直接存放数据，而MyISAM叶子节点存放的树数据对应 的地址注意：1、InnoDB是通过B+树结构对主键创建索引，然后叶子节点中存储记录，如果没有主键，则会选择唯一键，没有唯一键，则会生成一个6位数的row_id作为主键2、如果创建索引的键是其他字段，那么叶子节点中存储的是该记录的主键，通过主键索引找到对应的记录，此过程称之为回表

K55

0X0020

MySQL索引系统数据结构选型过程以及存在的弊端以及改进1、B树2、B+ 树