内容简介：本文主要讨论和MySQL存储引擎相关的数据结构，如B+Tree和一些FAQ和InnoDB的索引实现有关，底层使用B+Tree ，该结构最大的消耗在于频繁的改变树的节点（拆分、合并、转移位置），为了避免这种消耗较大的动作，尽可能的在插入新数据时不要对原有结构产生较大影响，如只是简单的append 到节点的数据集后面一般不会影响其他节点，或者至多产生一次分裂。 所以建议使用因为B+Tree的Secondary Index的叶子节点保存的是主键的内容，内容过大会影响存储空间，导致辅助索引过大，进而影响对副主索引的
本文主要讨论和 MySQL 存储引擎相关的数据结构，如B+Tree和一些FAQ
为什么不建议用UUID做主键？
和InnoDB的索引实现有关，底层使用B+Tree
，该结构最大的消耗在于频繁的改变树的节点（拆分、合并、转移位置），为了避免这种消耗较大的动作，尽可能的在插入新数据时不要对原有结构产生较大影响，如只是简单的append
到节点的数据集后面一般不会影响其他节点，或者至多产生一次分裂。
所以建议使用 单调递增
的数据作为主键，它很好的规避了对B+Tree存储主键时对树结构的变更操作。
为什么不建议用较长的字段做主键？
因为B+Tree的Secondary Index的叶子节点保存的是主键的内容，内容过大会影响存储空间，导致辅助索引过大，进而影响对副主索引的使用效率，如节点分配过多，范围查询检索性能降低等。
聚集索引怎么理解？
Clustered Index是InnoDB存储引擎中的索引，由于该引擎的存储使用B+Tree存储主键索引，且叶子节点中包括索引和数据两部分，就像数据「聚集」在索引上一样。也就是说InnoDB 的数据文件其实就是主键的索引文件，并且InnoDB中必须要有主键（否则就没有聚集索引一说了），如果用户不设置，则系统会自动设置隐形的6字节自增主键。 而非聚集索引则对应MyISAM中对索引的存储形式：叶子节点只存储主键的值，需要二次查询主键索引才可以获取数据信息。
同样都是使用B+Tree，InnoDB和MyISAM的实现细节有什么区别？
- 主键索引：主要区别是聚集索引和非聚集索引上，前者除了保存主键外还有数据，后者指保存主键的地址。
- 二级索引：前者叶节点中保存的是主键的值，后者保存的仍然是对应的主键的地址。 所以MyISAM的索引文件和数据文件是彼此独立存在的。
InnoDB的辅助索引的叶子节点存储主键的值而不是地址，好处是什么？
减少了当出现行记录移动或者数据页分裂时辅助索引的维护工作，虽然使用主键值当作指针会让辅助索引占用更多空间，但好处是，Innodb在移动行时无需更新辅助索引中的主键值，而MyISAM 需要调整其叶子节点中的地址。
B+Tree查找到非叶子节点时是否终止，B-Tree呢？
由于B-Tree的非叶子节点也存储数据，导致其左右子节点无需包含该父节点，所以B-Tree在检索到非叶子节点时如果命中条件则不会继续查找，直接返回。 而B+Tree由于非叶子节点不再存储数据，导致其及时是非叶子节点，最终也会在叶子节点中有一个完整（key和data）的节点，所以B+Tree 查找到非叶子节点即使命中条件，也需要继续向叶子节点处查找到对应key的那个数据节点才可以返回。
为什么说MyISAM的插入性能要好于InnoDB？
从底层对主键的维护说，InnoDB需要为新插入的数据的主键寻找合适的位置，可能会造成对数据结构的变动（节点拆分、转移、合并等）进而影响性能，而MyISAM 可以没有主键，所以在相同表结构前提下，一个没有主键不需要操心树结构的分裂重建问题，一个有主键需要考虑节点的分裂和重建等工作，前者性能高一些是合理的。
如何加快检索磁盘？
将每一个节点的大小和磁盘页的大小设置相同，保证每一次IO操作都可以加载完整的节点。 每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
为什么使用B-Tree(B+Tree)来存储索引而不用红黑树之类的?
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
首先说明一下B-Tree的渐进度的概念：
例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN) 。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。
一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。综上所述，用B-Tree作为索引结构效率是非常高的。
而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。
为什么说B+Tree比B-Tree更适合作为外存索引的数据结构？
原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小： dmax=floor(pagesize/(keysize+datasize+pointsize)) floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能（检索节点次数/IO次数降低）。
References
- http://blog.jobbole.com/105644/
本文首次发布于ElseF’s Blog, 作者 @stuartlau , 转载请保留原文链接.
以上所述就是小编给大家介绍的《B+Tree和B-Tree》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Docker——容器与容器云
浙江大学SEL实验室 / 人民邮电出版社 / 2015-9-1 / 89.00元
本书从实践者的角度，在讲解Docker高级实践技巧的同时，深入到源代码层次，为读者梳理出Docker容器技术和基于Docker的容器云技术（如Kubernetes）的实现方法和设计思路，帮助读者理解如何在实际场景中利用Docker解决问题并启发新的思考。全书包括两部分，第一部分深入解读Docker容器技术，包括Docker入门、架构总览、Docker容器核心原理解读，以及Docker高级实践技巧；......一起来看看 《Docker——容器与容器云》 这本书的介绍吧!
