一、得分点
B+树、叶子节点建立连接
二、标准回答
索引本质上就是通过预排序+树型结构来加快检索的效率,而MySQL中使用InnoDB和MyISAM引擎时都使用了B+树实现索引。它是一棵平衡多路查找树,是在二叉查找树基础上的改进数据结构。
在二叉查找树上查找一个数据时,最坏情况的查找次数为树的深度,当数据量很大时,查询次数可能还是很大,造成大量的磁盘IO,从而影响查询效率；
为了减少磁盘IO的次数,必须降低树的深度,因此在二叉查找树基础上将树改成了多叉加上一些限制条件,就形成了B树；
B+树中所有叶子节点值的总集就是全部关键字集合；
B+树为所有叶子节点增加了链接,从而实现了快速的范围查找；
在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接。
在数据库中,B+树的高度一般都在2～4层,这也就是说查找某一键值的行记录时最多只需要2到4次IO。
这很不错,因为当前一般的机械磁盘每秒至少可以做100次IO,2～4次的IO意味着查询时间只需0.02～0.04秒。
在数据库中,B+树索引还可以分为聚集索引和辅助索引,但不管是聚集索引还是辅助索引,其内部都是B+树的,即高度平衡的,叶子节点存放着所有的数据。
聚集索引与辅助索引不同的是,叶子节点存放的是否是一整行的信息。