-
Notifications
You must be signed in to change notification settings - Fork 0
/
mysqlxi-lie-san.html
320 lines (276 loc) · 20 KB
/
mysqlxi-lie-san.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="author" content="CatsAction" />
<meta property="og:type" content="article" />
<meta name="twitter:card" content="summary">
<meta name="keywords" content="数据库, 数据结构, MySQL, MySQL, " />
<meta property="og:title" content="MySQL系列三 - 索引"/>
<meta property="og:url" content="./mysqlxi-lie-san.html" />
<meta property="og:description" content="前述 本篇先讲解MySQL索引的三种数据结构实现：B+Tree索引、Hash索引、Full-Text索引。然后讲解InnoDB 和MyISAM存储引擎B+Tree索引的差异。最后浅谈索引优化。 MySQL的索引是存储引擎层而不是服务器层实现的。所以，并没有统一的索引标准。 MySQL索引数据结构 1: B+Tree索引 上图是一个简单的B+Tree结构，它有如下特点： 1）节点分内部节点和叶子节点。各叶子节点到根节点的高度一致。 2）内部节点不存储数据，只存储key，数据只存储在叶子节点上。 3）内部节点的key都是按从小到大的顺序排列的。对于一个给定的key，它的左子树的key都小于它，右子树的key都大于或等于它。 4）每个叶子节点都有一个指针指向下一个节点，方便顺序遍历和范围查询。 更多B+Tree结构的知识，参考文章B树和B+树的插入、删除图文详解 基于上述B+Tree的特点，B+Tree索引有如下优点： 1）内部节点不存储数据，可以容纳更多的索引项，可以定位更多的叶子节点，降低了树的高度 …" />
<meta property="og:site_name" content="CatsAction's blog" />
<meta property="og:article:author" content="CatsAction" />
<meta property="og:article:published_time" content="2019-08-13T00:00:00+08:00" />
<meta name="twitter:title" content="MySQL系列三 - 索引">
<meta name="twitter:description" content="前述 本篇先讲解MySQL索引的三种数据结构实现：B+Tree索引、Hash索引、Full-Text索引。然后讲解InnoDB 和MyISAM存储引擎B+Tree索引的差异。最后浅谈索引优化。 MySQL的索引是存储引擎层而不是服务器层实现的。所以，并没有统一的索引标准。 MySQL索引数据结构 1: B+Tree索引 上图是一个简单的B+Tree结构，它有如下特点： 1）节点分内部节点和叶子节点。各叶子节点到根节点的高度一致。 2）内部节点不存储数据，只存储key，数据只存储在叶子节点上。 3）内部节点的key都是按从小到大的顺序排列的。对于一个给定的key，它的左子树的key都小于它，右子树的key都大于或等于它。 4）每个叶子节点都有一个指针指向下一个节点，方便顺序遍历和范围查询。 更多B+Tree结构的知识，参考文章B树和B+树的插入、删除图文详解 基于上述B+Tree的特点，B+Tree索引有如下优点： 1）内部节点不存储数据，可以容纳更多的索引项，可以定位更多的叶子节点，降低了树的高度 …">
<title>MySQL系列三 - 索引 ·
CatsAction's blog
</title>
<link href="//netdna.bootstrapcdn.com/twitter-bootstrap/2.3.2/css/bootstrap-combined.min.css" rel="stylesheet">
<link rel="icon" type="image/x-icon" href="./theme/image/logo.ico" />
<link rel="stylesheet" type="text/css" href="./theme/css/elegant.prod.css" media="screen">
<link rel="stylesheet" type="text/css" href="./theme/css/custom.css" media="screen">
</head>
<body>
<div id="content">
<div class="navbar navbar-static-top">
<div class="navbar-inner">
<div class="container-fluid">
<a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</a>
<a class="brand" href="./"><span class=site-name>CatsAction's blog</span></a>
<div class="nav-collapse collapse">
<ul class="nav pull-right top-menu">
<li >
<a href=
.
>Home</a>
</li>
<li ><a href="./categories.html">Categories</a></li>
<li ><a href="./tags.html">Tags</a></li>
<li ><a href="./archives.html">Archives</a></li>
<li><form class="navbar-search" action="./search.html" onsubmit="return validateForm(this.elements['q'].value);"> <input type="text" class="search-query" placeholder="Search" name="q" id="tipue_search_input"></form></li>
</ul>
</div>
</div>
</div>
</div>
<div class="container-fluid">
<div class="row-fluid">
<div class="span1"></div>
<div class="span10">
<article itemscope>
<div class="row-fluid">
<header class="page-header span10 offset2">
<h1>
<a href="./mysqlxi-lie-san.html">
MySQL系列三
<small class="subtitle">
索引
</small>
</a>
</h1>
</header>
</div>
<div class="row-fluid">
<div class="span8 offset2 article-content">
<h2>前述</h2>
<p>本篇先讲解MySQL索引的三种数据结构实现：B+Tree索引、Hash索引、Full-Text索引。然后讲解InnoDB 和MyISAM存储引擎B+Tree索引的差异。最后浅谈索引优化。</p>
<p>MySQL的索引是存储引擎层而不是服务器层实现的。所以，并没有统一的索引标准。</p>
<h2>MySQL索引数据结构</h2>
<h5>1: B+Tree索引</h5>
<p><center>
<img alt="B+Tree" src="./images/b+tree.png">
</center></p>
<p>上图是一个简单的B+Tree结构，它有如下特点：</p>
<p>1）节点分内部节点和叶子节点。各叶子节点到根节点的高度一致。</p>
<p>2）内部节点不存储数据，只存储key，数据只存储在叶子节点上。</p>
<p>3）内部节点的key都是按从小到大的顺序排列的。对于一个给定的key，它的左子树的key都小于它，右子树的key都大于或等于它。</p>
<p>4）每个叶子节点都有一个指针指向下一个节点，方便顺序遍历和范围查询。</p>
<p>更多B+Tree结构的知识，参考文章<a href="https://www.cnblogs.com/nullzx/p/8729425.html">B树和B+树的插入、删除图文详解</a></p>
<p>基于上述B+Tree的特点，B+Tree索引有如下优点：</p>
<p>1）内部节点不存储数据，可以容纳更多的索引项，可以定位更多的叶子节点，降低了树的高度，从而减少了索引查询的IO次数。通常数据库的索引B+Tree高度是2或者3。</p>
<p>2）由于叶子节点之间有指针，方便遍历和范围查询，而且结果排序。</p>
<h5>2: Hash索引</h5>
<p>Hash索引有以下特点：</p>
<p>1）快，对于一个确定的Key，查询时间复杂度为O(1)。</p>
<p>2）索引是离散的，因此不支持范围查询和排序。</p>
<p>3）由于需要完整的key计算Hash值，因此Hash索引不支持匹配查询，只支持 =，IN 等值查询。</p>
<p>4）数据量比较大时，产生冲突的概率变大，维护Hash索引的成本变高。</p>
<blockquote>
<p>备注：Memory引擎默认索引即为Hash索引，InnoDB引擎提供自适应Hash索引。</p>
</blockquote>
<h5>3: Full-Text索引</h5>
<p>对于一个给定的key，如果希望匹配过滤查询，可以使用LIKE模糊匹配。但是由于B+Tree索引最左匹配的原则，类似%key%的查询，B+Tree索引将失效，因此此时需要全文索引。</p>
<p>MyISAM 和 InnoDB 存储引擎均支持全文索引，只在文本类型如char，varchar，text上可以应用全文索引。</p>
<h2>InnoDB B+Tree索引的分类</h2>
<h5>1: 主键索引</h5>
<p>在创建表的时候通过PRIMARY KEY指定。如果创建表时未指定主键，会选择一个非空的唯一索引作为主键，如果没有这样的索引，MySQL会创建一个数字id作为主键。每个表只能有一个主键。</p>
<p>InnoDB的主键是一种聚簇索引，它的叶子节点存储了key和对应的数据。关于聚簇索引，后面关于InnoDB和MYISAM B+Tree索引机制的差异会详细谈及。</p>
<h5>2: 唯一索引</h5>
<p>唯一索引相对主键索引，允许为空，且每个表能存在多个唯一索引。</p>
<h5>3: 普通索引</h5>
<p>普通索引相对于主键索引，叶子节点存储的是key和对应的主键id值，因此如果未索引覆盖，可能产生回表查询。下面先解释下索引覆盖和回表。</p>
<p>1）回表</p>
<p><center>
<img alt="jucu index" src="./images/jucu_index.png">
</center></p>
<p>上图是下面<code>user</code>表的主键索引和普通索引name的回表现象。</p>
<p>如果需要查询的是<code>SELECT id, name, sex FROM user WHERE name="zhangsan"</code>。此时由于sex列并不在普通索引name的key里面，因此需要再通过主键查询拿到具体的数据。这种两次查询的现象就叫回表。</p>
<p>MySQL有自己的查询优化器，当检查到查询字段太多，比如<code>SELECT * FROM table WHERE name=“zhangsan”</code>，优化器会选择直接通过主键索引查询，从而避免产生回表。可以通过<code>EXPLAIN</code>指令查看某一条SQL语句走的是哪一个索引。</p>
<div class="highlight"><pre><span></span><span class="k">CREATE</span> <span class="k">TABLE</span> <span class="nf">user</span> <span class="p">(</span>
<span class="n">id</span> <span class="kt">int</span> <span class="k">primary</span> <span class="k">key</span><span class="p">,</span>
<span class="n">name</span> <span class="kt">varchar</span><span class="p">(</span><span class="mi">20</span><span class="p">),</span>
<span class="n">sex</span> <span class="kt">varchar</span><span class="p">(</span><span class="mi">5</span><span class="p">),</span>
<span class="k">index</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
<span class="p">)</span><span class="kp">engine</span><span class="o">=</span><span class="n">innodb</span><span class="p">;</span>
</pre></div>
<p>2）索引覆盖</p>
<p>对于上面的查询，如果只查询id和name字段，那么普通索引name的key就能提供所需的字段，不需要再回表查询，这就是索引覆盖。为了查询sex时也能索引覆盖，我们可以建一个name和sex字段的多列索引。</p>
<p><em>参考资料:</em></p>
<p><a href="https://www.cnblogs.com/myseries/p/11265849.html">回表</a></p>
<p><a href="https://www.jianshu.com/p/486a514b0ded">MYSQL-B+TREE索引原理</a></p>
<h2>InnoDB和MyISAM索引差异</h2>
<p>下图是MyISAM引擎的索引图，图片来自网络，侵权请告知删除。</p>
<p><center>
<img alt="MyISAM index" src="./images/myisam_index.png">
</center></p>
<p>可以看到，MyISAM引擎的索引也是一种B+Tree数据结构，不过叶子节点存储的是key和行记录指针。这种叶子节点不储存行数据的索引称为非聚集索引，相对应的，InnoDB引擎的主键索引就是聚集索引，它的叶子节点存储key和行数据。</p>
<p>相对于InnoDB索引，当出现行移动或页分离时，数据移动更少。由于MyISAM的主键和普通索引都是相同的存储机制，因此对于普通索引，没有回表现象的产生。</p>
<blockquote>
<p>说明：页是MySQL的存储单元，默认大小为16k。对于InnoDB，逻辑存储结构是一个表空间，表空间包含段，区，页。页里面才是具体的行记录数据。</p>
</blockquote>
<h2>索引优化</h2>
<p>本节讲解一些索引优化技巧，相关内容来源于《高性能MySQL》。这里的索引仅仅指InnoDB存储引擎的B+Tree索引。</p>
<p>1）对于普通索引查询，尽可能使用索引覆盖，避免回表。</p>
<p>2）避免多个范围查询条件。</p>
<p>对于范围查询条件，MySQL无法再使用范围列后面的其它索引列了。我们可以把它改成多个等值条件查询，等值查询没有这个限制。如下面的age条件可以改成IN等值查询。</p>
<div class="highlight"><pre><span></span><span class="k">SELECT</span> <span class="n">id</span><span class="p">,</span> <span class="n">name</span><span class="p">,</span> <span class="n">age</span>
<span class="k">FROM</span> <span class="n">ueser</span>
<span class="k">WHERE</span> <span class="n">created_date</span> <span class="o">>=</span> <span class="s2">"2019-01-01"</span>
<span class="k">and</span> <span class="n">age</span> <span class="k">BETWEEN</span> <span class="mi">18</span> <span class="k">AND</span> <span class="mi">25</span><span class="p">;</span>
</pre></div>
<p>3）优化排序。索引可以用来排序，结合LIMIT限制提升性能。</p>
<p>4）由于最左匹配原则，对于多列索引，索引列的顺序很关键。因此，需要将选择性更高的列放在索引最前面。（为了避免随机IO和排序需要，可能这条就不适用了）</p>
<p>5）维护索引和表，整理数据碎片化（OPTIMIZE TABLE）。</p>
<h2>非索引查询优化</h2>
<p>1）避免查询不必要的记录。如返回所有的列，联表查询返回所有的列。</p>
<p>2）切分和分联关联查询。这条是为了上条避免查询不必要的记录。MySQL连接池作用，网络开销很小。避免磁盘IO应重于网络权重。</p>
<p>3）充分利用MySQL查询的优化器，关于优化器参考其他资料。</p>
<h2>后述</h2>
<p><em>参考资料：</em></p>
<p>《高性能MySQL》第五张和第六章</p>
<hr />
<aside>
<nav>
<ul class="articles-timeline">
<li class="previous-article">« <a href="./mysqlxi-lie-er.html"
title="Previous: MySQL系列二 - 事务和锁">MySQL系列二 <small class="subtitle">事务和锁</small></a></li>
<li class="next-article"><a href="./mysqlxi-lie-si.html"
title="Next: MySQL系列四 - 分区表和主从复制">MySQL系列四 <small class="subtitle">分区表和主从复制</small></a> »</li>
</ul>
</nav>
</aside>
</div>
<section id="article-sidebar" class="span2">
<h4>Published</h4>
<time itemprop="dateCreated" datetime="2019-08-13T00:00:00+08:00"> 8
13, 2019</time>
<!---->
<h4>Category</h4>
<a class="category-link"
href="./categories.html#mysql-ref">MySQL</a>
<h4>Tags</h4>
<ul class="list-of-tags tags-in-article">
<li><a href="./tags.html#mysql-ref">MySQL
<span>7</span>
</a></li>
<li><a href="./tags.html#shu-ju-jie-gou-ref">数据结构
<span>2</span>
</a></li>
<li><a href="./tags.html#shu-ju-ku-ref">数据库
<span>2</span>
</a></li>
</ul>
<h4>Stay in Touch</h4>
<div id="sidebar-social-link">
<a href="mailto:[email protected]" title="My Email Address" target="_blank" rel="nofollow noopener noreferrer">
<svg xmlns="http://www.w3.org/2000/svg" aria-label="Mail" role="img" viewBox="0 0 512 512"><rect width="512" height="512" rx="15%" fill="#328cff"/><path d="m250 186c-46 0-69 35-69 74 0 44 29 72 68 72 43 0 73-32 73-75 0-44-34-71-72-71zm-1-37c30 0 57 13 77 33 0-22 35-22 35 1v150c-1 10 10 16 16 9 25-25 54-128-14-187-64-56-149-47-195-15-48 33-79 107-49 175 33 76 126 99 182 76 28-12 41 26 12 39-45 19-168 17-225-82-38-68-36-185 67-248 78-46 182-33 244 32 66 69 62 197-2 246-28 23-71 1-71-32v-11c-20 20-47 32-77 32-57 0-108-51-108-108 0-58 51-110 108-110" fill="#fff"/></svg>
</a>
<a href="https://github.com/boyaziqi" title="catsaction Github Repository" target="_blank" rel="nofollow noopener noreferrer">
<svg xmlns="http://www.w3.org/2000/svg" aria-label="GitHub" role="img" viewBox="0 0 512 512"><rect width="512" height="512" rx="15%" fill="#1B1817"/><path fill="#fff" d="M335 499c14 0 12 17 12 17H165s-2-17 12-17c13 0 16-6 16-12l-1-50c-71 16-86-28-86-28-12-30-28-37-28-37-24-16 1-16 1-16 26 2 40 26 40 26 22 39 59 28 74 22 2-17 9-28 16-35-57-6-116-28-116-126 0-28 10-51 26-69-3-6-11-32 3-67 0 0 21-7 70 26 42-12 86-12 128 0 49-33 70-26 70-26 14 35 6 61 3 67 16 18 26 41 26 69 0 98-60 120-117 126 10 8 18 24 18 48l-1 70c0 6 3 12 16 12z"/></svg>
</a>
<a href="https://www.linkedin.com/feed/" title="My LinkedIn" target="_blank" rel="nofollow noopener noreferrer">
<svg xmlns="http://www.w3.org/2000/svg" aria-label="LinkedIn" role="img" viewBox="0 0 512 512" fill="#fff"><rect width="512" height="512" rx="15%" fill="#0077b5"/><circle cx="142" cy="138" r="37"/><path stroke="#fff" stroke-width="66" d="M244 194v198M142 194v198"/><path d="M276 282c0-20 13-40 36-40 24 0 33 18 33 45v105h66V279c0-61-32-89-76-89-34 0-51 19-59 32"/></svg>
</a>
</div>
<h4>Friendship Links</h4>
<ul class="list-of-tags tags-in-article">
<li>
<a href="https://leetcode-cn.com/" title="力扣中国站点" target="_blank" rel="nofollow noopener noreferrer">
LeetCode
</a>
</li>
<li>
<a href="https://coolshell.cn/about" title="陈皓酷壳" target="_blank" rel="nofollow noopener noreferrer">
CoolShell
</a>
</li>
<li>
<a href="https://yikun.github.io/" title="姜毅坤博客" target="_blank" rel="nofollow noopener noreferrer">
Yikun
</a>
</li>
<li>
<a href="https://www.nowcoder.com/" title="牛客网" target="_blank" rel="nofollow noopener noreferrer">
牛客网
</a>
</li>
</ul>
</section>
</div>
</article>
</div>
<div class="span1"></div>
</div>
</div>
</div>
<footer>
<div>
<span class="site-name">CatsAction's blog</span> - It's a wonderful world
</div>
<div id="fpowered">
Powered by: <a href="http://getpelican.com/" title="Pelican Home Page" target="_blank" rel="nofollow noopener noreferrer">Pelican</a>
Theme: <a href="https://elegant.oncrashreboot.com/" title="Theme Elegant Home Page" target="_blank" rel="nofollow noopener noreferrer">Elegant</a>
</div>
</footer> <script src="//code.jquery.com/jquery.min.js"></script>
<script src="//netdna.bootstrapcdn.com/twitter-bootstrap/2.3.2/js/bootstrap.min.js"></script>
<script>
function validateForm(query)
{
return (query.length > 0);
}
</script>
<script>
(function () {
if (window.location.hash.match(/^#comment-\d+$/)) {
$('#comment_thread').collapse('show');
}
})();
window.onhashchange=function(){
if (window.location.hash.match(/^#comment-\d+$/))
window.location.reload(true);
}
$('#comment_thread').on('shown', function () {
var link = document.getElementById('comment-accordion-toggle');
var old_innerHTML = link.innerHTML;
$(link).fadeOut(200, function() {
$(this).text('Click here to hide comments').fadeIn(200);
});
$('#comment_thread').on('hidden', function () {
$(link).fadeOut(200, function() {
$(this).text(old_innerHTML).fadeIn(200);
});
})
})
</script>
</body>
<!-- Theme: Elegant built for Pelican
License : MIT -->
</html>