企业建设网站的目的,深圳做网站收费,网站流量用完了,南通做外贸网站转载自 浅谈MySQL的B树索引与索引优化
MySQL的MyISAM、InnoDB引擎默认均使用B树索引#xff08;查询时都显示为“BTREE”#xff09;#xff0c;本文讨论两个问题#xff1a; 为什么MySQL等主流数据库选择B树的索引结构#xff1f; 如何基于索引结构#xff0c;理解常…转载自 浅谈MySQL的B树索引与索引优化
MySQL的MyISAM、InnoDB引擎默认均使用B树索引查询时都显示为“BTREE”本文讨论两个问题 为什么MySQL等主流数据库选择B树的索引结构 如何基于索引结构理解常见的MySQL索引优化思路
索引结构的选择基于这样一个性质大数据量时索引无法全部装入内存。 一、为什么索引无法全部装入内存
假设使用树结构组织索引简单估算一下 假设单个索引节点12B1000w个数据行unique索引则叶子节点共占约100MB整棵树最多200MB。 假设一行数据占用200B则数据共占约2G。
假设索引存储在内存中。也就是说每在物理盘上保存2G的数据就要占用200MB的内存索引:数据的占用比约为1/10。1/10的占用比算不算大呢物理盘比内存廉价的多以一台内存16G硬盘1T的服务器为例如果要存满1T的硬盘至少需要100G的内存远大于16G。 二、其他结构的问题
考虑到一个表上可能有多个索引、联合索引、数据行占用更小等情况实际的占用比通常大于1/10某些时候能达到1/3。在基于索引的存储架构中索引:数据的占用比过高因此索引无法全部装入内存。
由于无法装入内存则必然依赖磁盘或SSD存储。而内存的读写速度是磁盘的成千上万倍与具体实现有关因此核心问题是“如何减少磁盘读写次数”。
首先不考虑页表机制假设每次读、写都直接穿透到磁盘那么 线性结构读/写平均O(n)次 二叉搜索树BST读/写平均O(log2(n))次如果树不平衡则最差读/写O(n)次 自平衡二叉搜索树AVL在BST的基础上加入了自平衡算法读/写最大O(log2(n))次 红黑树RBT另一种自平衡的查找树读/写最大O(log2(n))次
BST、AVL、RBT很好的将读写次数从O(n)优化到O(log2(n))其中AVL和RBT都比BST多了自平衡的功能将读写次数降到最大O(log2(n))。
假设使用自增主键则主键本身是有序的树结构的读写次数能够优化到树高树高越低读写次数越少自平衡保证了树结构的稳定。如果想进一步优化可以引入B树和B树。 三、B树解决了什么问题 很多文章将B树误称为B-减树这可能是对其英文名“B-Tree”的误解更有甚者将B树称为二叉树或二叉搜索树。特别是与B树一起讲的时候。想当然的认为有B加树就有B-减树实际上B树的英文名是“B-Tree”。 如果抛开维护操作那么B树就像一棵“m叉搜索树”m是子树的最大个数时间复杂度为O(logm(n))。然而B树设计了一种高效简单的维护操作使B树的深度维持在约log(ceil(m/2))(n)~logm(n)之间大大降低树高。 再次强调 不要纠结于时间复杂度与单纯的算法不同磁盘IO次数才是更大的影响因素。读者可以推导看看B树与AVL的时间复杂度是相同的但由于B树的层数少磁盘IO次数少实践中B树的性能要优于AVL等二叉树。 同二叉搜索树类似每个节点存储了多个key和子树子树与key按顺序排列。
页表的目的是扩展内存加速磁盘读写。一个页Page通常4K等于磁盘数据块block的大小见inode与block的分析从磁盘读写的角度出发操作系统每次以页为单位将内容从磁盘加载到内存以摊分寻道成本修改页后再择期将该页写回磁盘。考虑到页表的良好性质可以使每个节点的大小约等于一个页使m非常大这每次加载的一个页就能完整覆盖一个节点以便选择下一层子树对子树同理。对于页表来说AVL或RBT相当于1个key2个子树的B树由于逻辑上相邻的节点物理上通常不相邻因此读入一个4k页页面内绝大部分空间都将是无效数据。
假设key、子树节点指针均占用4B则B树节点最大m * (4 4) 8m B页面大小4KB。则m 4 * 1024 / 8 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中数据行通常非常大存储数据行将减少页面中的子树个数m减小树高增大。假设数据行占用200B可忽略组织B树的指针则新的m 4 * 1024 / 200 20.48 ~ 21深度最大 log(21/2)(10^7) ~ 7。增加了一倍以上的IO不考虑。
方案2中节点增加了一个字段。假设是4B的指针则新的m 4 * 1024 / 12 341.33 ~ 341深度最大 log(341/2)(10^7) 3.14 ~ 4。与3差别不大可以考虑。
方案3的节点m与深度不变但时间复杂度变为稳定的O(logm(n))。考虑。
问题2
实际业务中范围查询的频率非常高B树只能定位到一个索引位置可能对应多行很难处理范围查询。给出2种方案 不改动查询的时候先查到左界再查到右界然后DFS或BFS遍历左界、右界之间的节点。 在“问题1-方案3”的基础上由于所有数据行都存储在叶子节点B树的叶子节点本身也是有序的可以增加一个指针指向当前叶子节点按主键顺序的下一叶子节点查询时先查到左界再查到右界然后从左界到有界线性遍历。
乍一看感觉方案1比方案2好——时间复杂度和常数项都一样方案1还不需要改动。但是别忘了局部性原理不管节点中存储的是数据行还是数据行位置方案2的好处在于叶子节点连续存储对页表和缓存友好。而方案1则面临节点逻辑相邻、物理分离的缺点。
引出B树
综上问题1的方案2与问题2的方案1可整合为一种方案基于B树的索引问题1的方案3与问题2的方案2可整合为一种基于B树的索引。实际上数据库、文件系统有些采用了B树有些采用B树。
由于某些猴子暂未明白的原因包括MySQL在内的主流数据库多选择了B树。即 主要变动如上所述 修改key与子树的组织逻辑将索引访问都落到叶子节点 按顺序将叶子节点串起来方便范围查询
B树和B树的增、删、查过程
B树的增删过程暂时可参考从B树、B树、B*树谈到R 树的“6、B树的插入、删除操作”小节B树的增删同理。此处暂不赘述。 五、Mysql索引优化
根据B树的性质很容易理解各种常见的MySQL索引优化思路。 暂不考虑不同引擎之间的区别。 优先使用自增key作为主键
前面的分析中假设用4B的自增key作为索引则m可达到512层高仅有3。使用自增的key有两个好处 自增key一般为int等整数型key比较紧凑这样m可以非常大而且索引占用空间小。最极端的例子如果使用50B的varchar包括长度那么m 4 * 1024 / 54m 75.85 ~ 76深度最大 log(76/2)(10^7) 4.43 ~ 5再加上cache缺失、字符串比较的成本时间成本增加较大。同时key由4B增长到50B整棵索引树的空间占用增长也是极为恐怖的如果二级索引使用主键定位数据行则空间增长更加严重。 自增的性质使得新数据行的插入请求必然落到索引树的最右侧发生节点分裂的频率较低理想情况下索引树可以达到“满”的状态。索引树满一方面层高更低一方面删除节点时发生节点合并的频率也较低。 优化经历 猴子曾使用varchar(100)的列做过主键存储containerId过了3、4天100G的数据库就满了DBA小姐姐邮件里委婉表示了对我的鄙视。。。之后增加了自增列作为主键containerId作为unique的二级索引时间、空间优化效果相当显著。 最左前缀匹配
索引可以简单如一个列(a)也可以复杂如多个列(a, b, c, d)即联合索引。如果是联合索引那么key也由多个列组成同时索引只能用于查找key是否存在相等遇到范围查询(、、between、like左匹配)等就不能进一步匹配了后续退化为线性查找。因此列的排列顺序决定了可命中索引的列数。
如有索引(a, b, c, d)查询条件a 1 and b 2 and c 3 and d 4则会在每个节点依次命中a、b、c无法命中d。也就是最左前缀匹配原则。
、in自动优化顺序
不需要考虑、in等的顺序mysql会自动优化这些条件的顺序以匹配尽可能多的索引列。
如有索引(a, b, c, d)查询条件c 3 and b 2 and a 1 and d 4与a 1 and c 3 and b 2 and d 4等顺序都是可以的MySQL会自动优化为a 1 and b 2 and c 3 and d 4依次命中a、b、c。
索引列不能参与计算
有索引列参与计算的查询条件对索引不友好甚至无法使用索引如from_unixtime(create_time) 2014-05-29。
原因很简单如何在节点中查找到对应key如果线性扫描则每次都需要重新计算成本太高如果二分查找则需要针对from_unixtime方法确定大小关系。
因此索引列不能参与计算。上述from_unixtime(create_time) 2014-05-29语句应该写成create_time unix_timestamp(2014-05-29)。
能扩展就不要新建索引
如果已有索引(a)想建立索引(a, b)尽量选择修改索引(a)为索引(a, b)。
新建索引的成本很容易理解。而基于索引(a)修改为索引(a, b)的话MySQL可以直接在索引a的B树上经过分裂、合并等修改为索引(a, b)。
不需要建立前缀有包含关系的索引
如果已有索引(a, b)则不需要再建立索引(a)但是如果有必要则仍然需考虑建立索引(b)。
选择区分度高的列作索引
很容易理解。如用性别作索引那么索引仅能将1000w行数据划分为两部分如500w男500w女索引几乎无效。
区分度的公式是count(distinct col) / count(*)表示字段不重复的比例比例越大区分度越好。唯一键的区分度是1而一些状态、性别字段可能在大数据面前的区分度趋近于0。 这个值很难确定一般需要join的字段要求是0.1以上即平均1条扫描10条记录。
