B+Tree

mysql索引数据结构–B+Tree

B+Tree是在BTree的基础之上做的一种优化，变化如下：

1、B+Tree每个节点可以包含更多的节点，这个做的原因有两个，第一个原因是为了降低树的高度，第二个原因是将数据范围变为多个区间，区间越多，数据检索越快

2、非叶子节点存储key，叶子节点存储key和数据

3、叶子节点两两指针相互连接（符合磁盘的预读特性），顺序查询性能更高

B+Tree

注意：在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

数据库中的树实践

已知Mysql中又三种数据引擎:

1. InnoDB

   InnoDB是事务型数据库的首选引擎，支持事务安全表（ACID），支持行锁定和外键，上图也看到了，InnoDB是默认的MySQL引擎

2. MyISAM

   MyISAM基于ISAM存储引擎，并对其进行扩展。它是在Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM拥有较高的插入、查询速度，但不支持事物。

3. Memory

   MEMORY存储引擎将表中的数据存储到内存中，未查询和引用其他表数据提供快速访问

主要说起其中两种数据库引擎

InnoDB — B+Tree 叶子节点直接放数据

注意：

1、InnoDB是通过B+Tree结构对主键创建索引，然后叶子节点中存储记录，如果没有主键，那么会选择唯一键，如果没有唯一键，那么会生成一个6位的row_id来作为主键

2、如果创建索引的键是其他字段，那么在叶子节点中存储的是该记录的主键，然后再通过主键索引找到对应的记录,叫做>>>回表

MyIASM----B+TREE