再有人问你为什么MySQL用B+树做索引，就把这篇文章发给她
|
B+树是对B树的进一步优化。让我们先来看下B+树的布局图：
按照上图我们来看下B+树和B树有什么差异。 1. B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不只存储键值，也会存储数据。之以是这么做是由于在数据库中页的巨细是牢靠的，innodb中页的默认巨细是16KB。假如不存储数据，那么就会存储更多的键值，响应的树的阶数(节点的子节点树)就会更大，树就会更矮更胖，云云一来我们查找数据举办磁盘的IO次数有会再次镌汰，数据查询的服从也会更快。其它，B+树的阶数是便是键值的数目的，假如我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一样平常根节点是常驻内存的，以是一样平常我们查找10亿数据，只必要2次磁盘IO。 2. 由于B+树索引的全部数据均存储在叶子节点，并且数据是凭证次序分列的。那么B+树使得范畴查找，排序查找，分组查找以及去重查找变得非常简朴。而B树由于数据分手在各个节点，要实现这一点是很不轻易的。 有意的读者也许还发明上图B+树中各个页之间是通过双向链表毗连的，叶子节点中的数据是通过单向链表毗连的。 着实上面的B树我们也可以对各个节点加上链表。其拭魅这些不是它们之前的区别，是由于在mysql的innodb存储引擎中，索引就是这样存储的。也就是说上图中的B+树索引就是innodb中B+树索引真正的实现方法，精确的说应该是聚积索引(聚积索引和非聚积索引下面会讲到)。 通过上图可以看到，在innodb中，我们通过数据页之间通过双向链表毗连以及叶子节点中数据之间通过单向链表毗连的方法可以找到表中全部的数据。 MyISAM中的B+树索引实现与innodb中的略有差异。在MyISAM中，B+树索引的叶子节点并不存储数据，而是存储数据的文件地点。 聚积索引 VS 非聚积索引 在上节先容B+树索引的时辰，我们提到了图中的索引着实是聚积索引的实现方法。那什么是聚积索引呢? 在MySQL中，B+树索引凭证存储方法的差异分为聚积索引和非聚积索引。 这里我们着重先容innodb中的聚积索引和非聚积索引。 1. 聚积索引(聚簇索引)：以innodb作为存储引擎的表，表中的数据城市有一个主键，纵然你不建设主键，体系也会帮你建设一个隐式的主键。这是由于innodb是把数据存放在B+树中的，而B+树的键值就是主键，在B+树的叶子节点中，存储了表中全部的数据。这种以主键作为B+树索引的键值而构建的B+树索引，我们称之为聚积索引。 2. 非聚积索引(非聚簇索引)：以主键以外的列值作为键值构建的B+树索引，我们称之为非聚积索引。非聚积索引与聚积索引的区别在于非聚积索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还必要按照主键再去聚积索引中举办查找，这个再按照聚积索引查找数据的进程，我们称为回表。 大白了聚积索引和非聚积索引的界说，我们应该大白这样一句话：数据即索引，索引即数据。 操作聚积索引和非聚积索引查找数据 前面我们讲授B+树索引的时辰并没有去说怎么在B+树中举办数据的查找，首要就是由于还没有引出聚积索引和非聚积索引的观念。下面我们通过讲授怎样通过聚积索引以及非聚积索引查找数据表中数据的方法先容一下B+树索引查找数据要领。 操作聚积索引查找数据
照旧这张B+树索引图，此刻我们应该知道这就是聚积索引，表中的数据存储在个中。此刻假设我们要查找id>=18而且id<40的用户数据。对应的sql语句为select * from user where id>=18 and id <40，个中id为主键。详细的查找进程如下：
从内存中读取到页1，要查找这个id>=18 and id <40可能范畴值，我们起首必要找到id=18的键值。 从页1中我们可以找到键值18，此时我们必要按照指针p2，定位到页3。
从磁盘中读取页3后将页3放入内存中，然后举办查找，我们可以找到键值18，然后再拿到页3中的指针p1，定位到页8。
将页8读取到内存中后。 由于页中的数据是链表举办毗连的，并且键值是凭证次序存放的，此时可以按照二分查找法定位到键值18。 此时由于已经到数据页了，此时我们已经找到一条满意前提的数据了，就是键值18对应的数据。 由于是范畴查找，并且此时全部的数据又都存在叶子节点，而且是有序分列的，那么我们就可以对页8中的键值依次举办遍历查找并匹配满意前提的数据。 （编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
