索引底层原理解析之B+Tree

索引原理 index

返回数据：

结果实现了根据id主键进行排序，增加了查询速率；
1.原理：
1.将数据分成三部分进行存储;主键,当前数据，指针。然后通过指针将数据连接起来。增加了查询速度，此时的时间复杂度是O(n),所以数据量大了过后，速率就减慢了。引申出页的管理，默认将大小为16kb的数据放入一个页里面进行管理。然后将这些页放入一个页目录中进行管理。页目录只存放索引的id和指针。这样数据进来，就先判断页目录，确定大致位置，然后去页里面进行查询。以此类推，页目录的数据会越来越多从而形成树的结构，这种树结构称为B+树。一般树的深度为2-4层。最后一层没有节点的称为叶子节点。B树任意节点都存放完整的数据，这也是B树与B+树最大的区别，存完整数据的话，页里面存的数据就就减少了，树的深度就增加了，从而影响了查询效率。B+树的非叶子节点只存储索引和指针信息，所以可以说B+树是对B树的一种优化。

注意：B+树的深度一般是2-4层，innodb引擎设计时将根节点常驻内存，所以查找某一个键值行时最多需要1-3次磁盘I/O操作，因为根节点不需要进行磁盘操作

2.B+树与B树的几点不同：
a.非叶子节点只存储键值信息。
b.所有的叶子节点都有一个链指针
为什么b+树的叶节点要用指针连起来，而b树的叶节点却不用？
B+树只有叶结点存储数据。叶结点连起来正好是所有数据的有序序列，可以用来做全表顺序扫描或者范围查询。
B树的数据存储在各层结点上，叶结点只有部分数据，连起来也没有任何用处。
c.数据记录都存放在叶子节点上。