浅聊MySQL的B树索引与索引优化小结
发布时间：2022-03-08 02:39:23 所属栏目：MySql教程 来源：互联网
导读：MySQL的MyISAM、InnoDB引擎默认均使用B+树索引（查询时都显示为BTREE），本文讨论两个问题： 为什么MySQL等主流数据库选择B+树的索引结构？ 如何基于索引结构，理解常见的MySQL索引优化思路？ 为什么索引无法全部装入内存 索引结构的选择基于这样一个性质：
|
MySQL的MyISAM、InnoDB引擎默认均使用B+树索引（查询时都显示为“BTREE”），本文讨论两个问题： 为什么MySQL等主流数据库选择B+树的索引结构？ 如何基于索引结构，理解常见的MySQL索引优化思路？ 为什么索引无法全部装入内存 索引结构的选择基于这样一个性质：大数据量时，索引无法全部装入内存。 为什么索引无法全部装入内存？假设使用树结构组织索引，简单估算一下： 假设单个索引节点12B，1000w个数据行，unique索引，则叶子节点共占约100MB，整棵树最多200MB。 假设一行数据占用200B，则数据共占约2G。 假设索引存储在内存中。也就是说，每在物理盘上保存2G的数据，就要占用200MB的内存，索引:数据的占用比约为1/10。1/10的占用比算不算大呢？物理盘比内存廉价的多，以一台内存16G硬盘1T的服务器为例，如果要存满1T的硬盘，至少需要100G的内存，远大于16G。 考虑到一个表上可能有多个索引、联合索引、数据行占用更小等情况，实际的占用比通常大于1/10，某些时候能达到1/3。在基于索引的存储架构中，索引:数据的占用比过高，因此，索引无法全部装入内存。 其他结构的问题 由于无法装入内存，则必然依赖磁盘（或SSD）存储。而内存的读写速度是磁盘的成千上万倍（与具体实现有关），因此，核心问题是“如何减少磁盘读写次数”。 再次强调： 不要纠结于时间复杂度，与单纯的算法不同，磁盘IO次数才是更大的影响因素。读者可以推导看看，B树与AVL的时间复杂度是相同的，但由于B树的层数少，磁盘IO次数少，实践中B树的性能要优于AVL等二叉树。 同二叉搜索树类似，每个节点存储了多个key和子树，子树与key按顺序排列。 页表的目录是扩展外存+加速磁盘读写，一个页（Page）通常4K（等于磁盘数据块block的大小，见inode与block的分析），操作系统每次以页为单位将内容从磁盘加载到内存（以摊分寻道成本），修改页后，再择期将该页写回磁盘。考虑到页表的良好性质，可以使每个节点的大小约等于一个页（使m非常大），这每次加载的一个页就能完整覆盖一个节点，以便选择下一层子树；对子树同理。对于页表来说，AVL（或RBT）相当于1个key+2个子树的B树，由于逻辑上相邻的节点，物理上通常不相邻，因此，读入一个4k页，页面内绝大部分空间都将是无效数据。 假设key、子树节点指针均占用4B，则B树节点最大m * (4 + 4) = 8m B；页面大小4KB。则m = 4 * 1024 / 8m = 512，一个512叉的B树，1000w的数据，深度最大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如AVL的深度为log(2)(10^7) = 23.25 ~= 24，相差了5倍以上。震惊！B树索引深度竟然如此！ 另外，B树对局部性原理非常友好。如果key比较小（比如上面4B的自增key），则除了页表的加成，缓存还能进一步预读加速。美滋滋~ B+树解决了什么问题 B树的剩余问题 然而，如果要实际应用到数据库的索引中，B树还有一些问题： 未定位数据行 无法处理范围查询 问题1 数据表的记录有多个字段，仅仅定位到主键是不够的，还需要定位到数据行。有3个方案解决： 直接将key对应的数据行（可能对应多行）存储子节点中。 数据行单独存储；节点中增加一个字段，定位key对应数据行的位置。 修改key与子树的判断逻辑，使子树大于等于上一key小于下一key，最终所有访问都将落于叶子节点；叶子节点中直接存储数据行或数据行的位置。 方案1直接pass，存储数据行将减少页面中的子树个数，m减小树高增大。 方案2的节点中增加了一个字段，假设是4B的指针，则新的m = 4 * 1024 / 12m = 341.33 ~= 341，深度最大 log(341/2)(10^7) = 3.14 ~= 4。 方案3的节点m与深度不变，但时间复杂度变为稳定的O(logm(n))。 方案3可以考虑。 问题2 实际业务中，范围查询的频率非常高，B树只能定位到一个索引位置（可能对应多行），很难处理范围查询。改动较小的是2个 方案： 不改动；查询的时候先查到左界，再查到右界，然后DFS（或BFS）遍历左界、右界之间的节点。 在“问题1-方案3”的基础上，由于所有数据行都存储在叶子节点，B树的叶子节点本身也是有序的，可以增加一个指针，指向当前叶子节点按主键顺序的下一叶子节点；查询时先查到左界，再查到右界，然后从左界到有界线性遍历。 乍一看感觉方案1比方案2好——时间复杂度和常数项都一样，方案1还不需要改动。但是别忘了局部性原理，不管节点中存储的是数据行还是数据行位置，方案2的好处在于，依然可以利用页表和缓存预读下一节点的信息。而方案1则面临节点逻辑相邻、物理分离的缺点。 （编辑：财气旺网 - 财气网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐