讯享网

 <p id="2E50EVKC">作者：京东云开发者-京东零售 韩航云</p><p id="2E50EVKD">链接：https://my.oschina.net/u//blog/</p><p>一、索引到底是什么</p><p id="2E50EVKE">. 索引是帮助 mysql 高效获取数据的排好序的数据结构</p><p id="2E50EVKF">. 索引是存储在文件里的</p><p id="2E50EVKG">. 数据结构： 二叉树 HASH BTREE</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2Fb3fbb4c4j00s7pr21003zd200u000eqg00id0090.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVKI">如果没有索引的话，循环一条一条的找，找一次就是一次 IO，这样速度就会很慢</p><p id="2E50EVKJ">我们知道数据库数据都是存在磁盘上的，当我们查找数据时，就会从磁盘上取数据，每取一次就是一次 IO，IO 是非常耗时的，为了速度快会把数据放到缓存里，然后在缓存里进行操作</p><p>二、磁盘存取原理</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F1e9565daj00s7prd200u000fbg00id009d.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVKL">当查找数据的时候，就是磁头循环找此道，就会一直循环查找，一次查找就是一次 IO，IO 是很耗时的</p><p>三、Mysql 数据结构详解</p><p id="2E50EVKM">就拿上面的 7 条数据来说，如果没有索引，当我们查找第 7 条数据时，就会循环 7 次，如果有百万级别的数据，那么就会查找百万次，显然这样是不行的，就需要数据结构算法来优化，那我们就从二叉树 ----HASH---BTREE 来一一说起</p><p id="2E50EVKN">二叉树：</p><p id="2E50EVKO">二叉树节点保存的都是单个索引，高度会随着数据增大而增高，但是比一条一条的循环会快</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2Fb5b92e83j00s7pr23004ud200u000hrg00id00av.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F05affa7fj00s7prd200go009fg00go009f.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVKR">不用二叉树是因为的极端情况下会出现单边增长，这样在数量大的情况下，和一条一条查找没有区别。</p><p id="2E50EVKS">红黑树：</p><p id="2E50EVKT">红黑树有自平衡性质，不会出现单边增长，它会动态自旋转，在性能上比二叉树又高一点，但是 mysql 也没有用这种数据结构，因为数据量超大的情况下，数据高度也会一直增大，在最终这个树高度也非常大，解决不了根本问题</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2Fedd5bc45j00s7pr24000yd200go0082g00go0082.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVKV">HASH:</p><p id="2E50EVL0">hash 算法一次就会定位到文件指针，速度快，但是还是没有用，如果范围查找的话就没有办法了，如果只是内存中的话，他的时间复杂度是 O (1), 速度会会很快，但是索引文件也是保存在磁盘上，而且 hash 是不连续的放在磁盘上的，这样查询起来也很慢，这才是不用 hash 的最根本原因</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F9d90d93fj00s7pr26004sd200u000fqg00id009m.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVL2">B-TREE:</p><p id="2E50EVL3">相比上面的数据结构，b-tree 增加了横向大小（度 Degree），那么在高度上就减小了，查找次数就少了</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2Fb6j00s7pr27001td200go007wg00go007w.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVL5">15，56，77.。。。。是索引，data 就是对应的一行数据</p><p id="2E50EVL6">那么在横向的度上最大多少合适呢？？总不能横向上一直扩展下呀，磁盘一次 IO，就是取一个横向的节点（度），把一个节点的数据放在缓存中，那么一次 IO 也不能把所用的数据全取出来，所以最好是一次 io，就把这个节点全取处理，电脑操作系统从磁盘一次取数据到内存中一般是 4K，而 mysql 取一次数据一般是 16K，所以横向节点一般设置为 16K。 因为一个节点设置成 16K 的话，这个节点保存了索引和索引对应行的数据，那么这个节点横向保存不了太多的数据，所以，这种数据结构也不合适，引入新的数据结构</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F3e5c9052j00s7pr28008id200u000frg00id009n.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVL8">B+Tree</p><p id="2E50EVL9">查找一次数据就是和磁盘一次 IO，一次 IO 会把这个数据相邻的数据一下全部查处理，这样速度会更快，这样的一页就是咱们说的一个节点（4K），分配空间的时候也是一页一页分配的，这样会更快，一页就是一个节点</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F9b82fdbbj00s7pr29006ud200u000f6g00id009a.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVLB">mysql 常用的引擎有 MyISAM 和 InNoDb, 两种引擎得索引结构是不一样的</p><p id="2E50EVLC">MyISAM 的数据结构：</p><p id="2E50EVLD">.frm 表结构文件 .myd 表数据文件 .myi 表索引文件</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F512cfbb0j00s7pr2b00cyd200t800ksg00id00d1.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F6082ca71j00s7pr2c0079d200u000f3g00id0098.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVLG">myisam 引擎的主键索引数据结构是左上图，普通索引是右上图，叶子节点存的不是数据本身，是数据文件指针，和 b_tree 数据不一样，注意：每类的索引，都是各自的树，不是混合在一起的</p><p id="2E50EVLH">.frm 表结构文件 .ibd 表数据和索引文件</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F66dfd4d4j00s7pr2d007wd200tk00e2g00id008q.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2F89aa87d5j00s7pr2f00c5d200u000hug00id00aw.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVLK">主键索引是聚集索引，因为叶子节点是所有的数据，就是一行数据，非主键索引叶子节点只包括索引和主键，再用主键找对应数据</p><p id="2E50EVLL">非主键索引叶子节点只包括索引和主键，再用主键找对应数据，这样是为了节省空间和数据一致性</p><p id="2E50EVLM">联合索引：</p><p id="2E50EVLN">要满足最左原则</p><p id="2E50EVLO">联合索引 (col1, col2, col3) 也是一棵 B + 树，其非叶子节点存储的是第一个关键字的索引，而叶子节点存储的则是三个关键字 col1、col2、col3 三个关键字的数据，且按照 col1-col2-col3 的顺序进行排序。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0123%2Fe4c605e9j00s7pr2g004fd200u000efg00id008t.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2E50EVLQ">例如：</p><p id="2E50EVLR">如果执行的是，SELECT * FROM T WHERE B=‘Tom’ AND C=4567;</p><p id="2E50EVLS">那么无法使用索引，因为索引是用 A 字段先排序的，如果没有先确定 A，直接查找 B 和 C，那么将会是全表查询。</p><p id="2E50EVLT">如果执行的是，SELECT * FROM T WHERE A=‘30’ ;</p><p id="2E50EVLU">那么，会先找到 A 字段，再在 A 等于 30 的数据中（比如有很多条），找 B 等于 Demi 的数据。这样是可以用到索引的。</p><p id="2E50EVLV">如果执行的是，SELECT * FROM T WHERE A=‘18’ AND C=1234;</p><p id="2E50EVM0">那么，A 字段可以索引，而 C 不能索引。所以可以部分索引，也比全表查询快。</p><p id="2E50EVM1">如果执行 SELECT * FROM T WHERE B=Demi AND C=1234 and A=‘18’</p><p id="2E50EVM2">是用到索引的，在 and 的情况下如果把第一个放到最后位置也是能用到索引的</p><p id="2E50EVM3">现在我想大家应该了解了什么为什么是最左原则。因为，B + 树是按照最左边的字段以此构建的。</p>