回答思路

得分点 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+树的，即高度平衡的，叶子节点存放着所有的数据。聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的信息。