MySQL 数据库索引 -- B+树模型

这时我们需要：

1、定位到记录所在的页

2、从页内查找相应的记录

在前面我们知道了为了主键快速一条记录在页中的位置而设立页目录，类似的办法，为了定位一条记录在所在的数据页我们也可以建立一个别的目录，在建立这个目录的过程中，我们必须做2件事情：

上文叙述的目录项和用户记录长得挺像，只不过目录项中的两个列是主键和页号。所以，我们可以直接复用之前的数据页来存储目录项。采用 record_type 字段区分普通的记录

同时，目录项的 min_rec_flag 为1，普通记录都为0

上面的数据结构就是B+树，真正用来存放用户记录的都是B+树最底层的叶子节点，其余用来存放目录项记录的节点称为非叶子节点或者内节点，最上边的节点称为根节点。

这里我们假设一个数据页，只能存3条记录，实际上一个页可以存很多条记录。假设一个数据页可以存100条用户记录，1000条目录项记录，那么：

如果B+树只有1层，则最多存放 100 条用户记录

如果B+树只有2层，则最多能存放 1000 * 100 =

如果B+树只有3层，则最多能存放 1000 * 1000 * 100 =

如果B+树只有4层，则最多能存放 1000 * 1000 * 1000 * 100 =

所以，我们一般用到的B+树不会超过4层，也就意味着通过主键查找记录时，最多只需要进行4个页面的查找就可以找到。

InnoDB 会自动为主键或者带有 UNIQUE 属性的列建立索引。

KEY 和 INDEX 是同义词，创建索引命名时以 idx 为前缀，后面跟着需要建立索引的列名，且多个列名之间用下划线隔开。

也可以在修改表结构的时候添加索引

最后，删除这个索引。

在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binarysearchtree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写 *** 作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

综上所述，B-树是B树的别名，二者指的是一棵树。

---