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