-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.html
2356 lines (1067 loc) · 132 KB
/
index.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
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html class="theme-next mist use-motion" lang="zh-Hans">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">
<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
<link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />
<link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />
<link href="/css/main.css?v=5.1.2" rel="stylesheet" type="text/css" />
<meta name="keywords" content="Hexo, NexT" />
<link rel="alternate" href="/atom.xml" title="EWSUN" type="application/atom+xml" />
<link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.1.2" />
<meta name="description" content="有所舍，有所爱，做一个感性的码农">
<meta property="og:type" content="website">
<meta property="og:title" content="EWSUN">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="EWSUN">
<meta property="og:description" content="有所舍，有所爱，做一个感性的码农">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="EWSUN">
<meta name="twitter:description" content="有所舍，有所爱，做一个感性的码农">
<script type="text/javascript" id="hexo.configurations">
var NexT = window.NexT || {};
var CONFIG = {
root: '/',
scheme: 'Mist',
version: '5.1.2',
sidebar: {"position":"left","display":"post","offset":12,"offset_float":12,"b2t":false,"scrollpercent":false,"onmobile":false},
fancybox: true,
tabs: true,
motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn"}},
duoshuo: {
userId: '0',
author: '博主'
},
algolia: {
applicationID: '',
apiKey: '',
indexName: '',
hits: {"per_page":10},
labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
}
};
</script>
<link rel="canonical" href="http://yoursite.com/"/>
<title>EWSUN</title>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">
<div class="container sidebar-position-left
page-home">
<div class="headband"></div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-wrapper">
<div class="site-meta ">
<div class="custom-logo-site-title">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<span class="site-title">EWSUN</span>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<p class="site-subtitle"></p>
</div>
<div class="site-nav-toggle">
<button>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section">
<i class="menu-item-icon fa fa-fw fa-home"></i> <br />
首页
</a>
</li>
<li class="menu-item menu-item-about">
<a href="/about/" rel="section">
<i class="menu-item-icon fa fa-fw fa-user"></i> <br />
关于
</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section">
<i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
标签
</a>
</li>
<li class="menu-item menu-item-categories">
<a href="/categories/" rel="section">
<i class="menu-item-icon fa fa-fw fa-th"></i> <br />
分类
</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section">
<i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
归档
</a>
</li>
<li class="menu-item menu-item-schedule">
<a href="/schedule/" rel="section">
<i class="menu-item-icon fa fa-fw fa-calendar"></i> <br />
日程表
</a>
</li>
<li class="menu-item menu-item-sitemap">
<a href="/sitemap.xml" rel="section">
<i class="menu-item-icon fa fa-fw fa-sitemap"></i> <br />
站点地图
</a>
</li>
<li class="menu-item menu-item-commonweal">
<a href="/404/" rel="section">
<i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br />
公益404
</a>
</li>
</ul>
</nav>
</div>
</header>
<main id="main" class="main">
<div class="main-inner">
<div class="content-wrap">
<div id="content" class="content">
<section id="posts" class="posts-expand">
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/07/30/mysql/Mysql索引背后的数据结构及算法原理/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="EtanWatson">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/header.png">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="EWSUN">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/07/30/mysql/Mysql索引背后的数据结构及算法原理/" itemprop="url">未命名</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2018-07-30T11:32:11+08:00">
2018-07-30
</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="Mysql索引背后的数据结构及算法原理"><a href="#Mysql索引背后的数据结构及算法原理" class="headerlink" title="Mysql索引背后的数据结构及算法原理"></a>Mysql索引背后的数据结构及算法原理</h1><h2 id="MySql支持的索引"><a href="#MySql支持的索引" class="headerlink" title="MySql支持的索引"></a>MySql支持的索引</h2><h3 id="哈希索引"><a href="#哈希索引" class="headerlink" title="哈希索引"></a>哈希索引</h3><h3 id="全文索引"><a href="#全文索引" class="headerlink" title="全文索引"></a>全文索引</h3><h3 id="BTree索引"><a href="#BTree索引" class="headerlink" title="BTree索引"></a>BTree索引</h3><h4 id="数据结构及算法理论层面讨论MYSql数据库的索引的数理基础"><a href="#数据结构及算法理论层面讨论MYSql数据库的索引的数理基础" class="headerlink" title="数据结构及算法理论层面讨论MYSql数据库的索引的数理基础"></a>数据结构及算法理论层面讨论MYSql数据库的索引的数理基础</h4><h5 id="索引"><a href="#索引" class="headerlink" title="索引"></a>索引</h5><p>索引（Index）是帮助MySQL高效获取数据的<strong>数据结构</strong><br>数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。<br><img src="/images/15329215953027.jpg" alt=""></p>
<p>二叉查找树</p>
<h5 id="Btree"><a href="#Btree" class="headerlink" title="Btree"></a>Btree</h5><p>为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：</p>
<ol>
<li><p>d为大于1的一个正整数，称为B-Tree的度。</p>
</li>
<li><p>h为一个正整数，称为B-Tree的高度。</p>
</li>
<li><p>每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。</p>
</li>
<li><p>每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。</p>
</li>
<li><p>所有叶节点具有相同的深度，等于树高h。</p>
</li>
<li><p>key和指针互相间隔，节点两端是指针。</p>
</li>
<li><p>一个节点中的key从左到右非递减排列。</p>
</li>
<li><p>所有节点组成树结构。</p>
</li>
<li><p>每个指针要么为null，要么指向另外一个节点。</p>
</li>
<li><p>如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)，其中v(key1)为node的第一个key的值。</p>
</li>
<li><p>如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。</p>
</li>
<li><p>如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。</p>
</li>
</ol>
<h6 id="Btree按key检索数据"><a href="#Btree按key检索数据" class="headerlink" title="Btree按key检索数据"></a>Btree按key检索数据</h6><ol>
<li>首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。</li>
<li><p>伪代码</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line">Btree_Search(node, key){</div><div class="line"> if(node == null) return null;</div><div class="line"> foreach(node.key){</div><div class="line"> if(node.key[i] == key) return node.data[i];</div><div class="line"> if(node.key[i] > key ) return Btree_Search(point[i] -> node);</div><div class="line"> }</div><div class="line"> return BTree_Search(point[i+1]->node);</div><div class="line">}</div><div class="line">data = BTree_Search(root,my_key);</div></pre></td></tr></table></figure>
</li>
</ol>
<ol>
<li>性质：关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为<strong>logd((N+1)/2)</strong>，检索一个key，其查找节点个数的渐进复杂度为<strong>O(logdN)</strong>。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。</li>
<li>插入和删除<br>另外，由于插入删除新的数据记录会<strong>破坏B-Tree的性质</strong>，因此在插入删除时，需要对树进行一个<strong>分裂、合并、转移</strong>等操作以保持B-Tree性质<h5 id="B-Tree"><a href="#B-Tree" class="headerlink" title="B+Tree"></a>B+Tree</h5></li>
<li>每个节点的指针上限为2d而不是2d+1。</li>
<li>内节点不存储data，只存储key；叶子节点不存储指针。 </li>
</ol>
<p><img src="/images/15329216173368.jpg" alt=""></p>
<p>由于并不是所有节点都具有相同的域，因此B+Tree中<strong>叶节点和内节点一般大小不同</strong>。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对<strong>每个节点申请同等大小的空间</strong>。一般来说，B+Tree比B-Tree更适合实现外存储索引结构 </p>
<h6 id="带有顺序访问指针的B-Tree"><a href="#带有顺序访问指针的B-Tree" class="headerlink" title="带有顺序访问指针的B+Tree"></a>带有顺序访问指针的B+Tree</h6><p>一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。<br><img src="/images/15329216322039.jpg" alt=""></p>
<p>在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高<strong>区间访问的性能</strong>，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率</p>
<h6 id="为什么使用B-Tree"><a href="#为什么使用B-Tree" class="headerlink" title="为什么使用B-Tree"></a>为什么使用B-Tree</h6><ol>
<li>索引往往以索引文件的形式存储的磁盘上</li>
<li>索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。</li>
<li>从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。下图展示了一个4 x 4的主存模型。<img src="/images/15329216588169.jpg" alt=""></li>
</ol>
<ol>
<li>主存的存取过程如下<br>当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定 位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。<br>写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。<br>这里可以看出，主存存取的时间仅与存取次数呈线<strong>性关系</strong>，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，<strong>先取A0再取A1和先取A0再取D3</strong>的时间消耗是一样的。</li>
<li>磁盘存取原理<ol>
<li>局部性原理与磁盘预读：由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的<strong>局部性原理</strong>：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为<strong>4k</strong>），<strong>主存和磁盘以页为单位交换数据</strong>。当程序要读取的数据不在主存中时，会触发一个<strong>缺页异常</strong>，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。</li>
<li>B-/+Tree索引的性能分析<br>每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。<strong>B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存）</strong>，渐进复杂度为<strong>O(h)=O(logdN)</strong>。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）</li>
<li>红黑树<br>而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。</li>
<li>B+Tree<br>B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小：由于<strong>B+Tree内节点去掉了data域</strong>，因此可以拥有更大的出度，拥有更好的性能。</li>
</ol>
</li>
</ol>
<h4 id="结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题"><a href="#结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题" class="headerlink" title="结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题"></a>结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题</h4><h5 id="MySql索引实现"><a href="#MySql索引实现" class="headerlink" title="MySql索引实现"></a>MySql索引实现</h5><h6 id="MyISAM索引实现"><a href="#MyISAM索引实现" class="headerlink" title="MyISAM索引实现"></a>MyISAM索引实现</h6><p>MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：<br><img src="/images/15329217134887.jpg" alt=""></p>
<p>可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：<br><img src="/images/15329217447787.jpg" alt=""></p>
<p>同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。</p>
<h6 id="InnoDB索引实现"><a href="#InnoDB索引实现" class="headerlink" title="InnoDB索引实现"></a>InnoDB索引实现</h6><ol>
<li>虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。<br>第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。<br>下图是InnoDB主索引（同时也是数据文件）的示意图，<strong>可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引</strong>。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。<br><img src="/images/15329217797482.jpg" alt=""></li>
</ol>
<ol>
<li>InnoDB的辅助索引data域存储相应记录主键的值而不是地址<br>InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：<br><img src="/images/15329217930256.jpg" alt=""></li>
</ol>
<p>聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。</p>
<h6 id="从索引实现方式而了解到的"><a href="#从索引实现方式而了解到的" class="headerlink" title="从索引实现方式而了解到的"></a>从索引实现方式而了解到的</h6><ol>
<li>不建议使用过长的字段作为主键<br>所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大</li>
<li>用非单调的字段作为主键在InnoDB中不是个好主意：因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而<strong>频繁的分裂调整</strong>，十分低效，而使用自增字段作为主键则是一个很好的选择。</li>
</ol>
<h4 id="高性能使用索引的策略"><a href="#高性能使用索引的策略" class="headerlink" title="高性能使用索引的策略"></a>高性能使用索引的策略</h4><h5 id="结构优化"><a href="#结构优化" class="headerlink" title="结构优化"></a>结构优化</h5><ol>
<li>示例数据库<br><img src="/images/15329219116556.jpg" alt=""></li>
</ol>
<ol>
<li><p>最左前缀原理与相关优化<br>高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line">SHOW INDEX FROM employees.titles;</div><div class="line">ALTER TABLE employees.titles DROP INDEX emp_no;</div></pre></td></tr></table></figure>
<ol>
<li><p>全列匹配</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26';</div></pre></td></tr></table></figure>
<p> 很明显，当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。这里有一点需要注意，理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引，例如我们将where中的条件顺序颠倒,效果是一样的.</p>
</li>
<li>最左前缀匹配<br> 当查询条件精确匹配索引的左边连续一个或几个列时，如<emp_no>或<emp_no, title="">，所以可以被用到，但是只能用到一部分，即条件所组成的最左前缀。上面的查询从分析结果看用到了PRIMARY索引，但是key_len为4，说明只用到了索引的第一列前缀。</emp_no,></emp_no></li>
<li><p>查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。<br>此时索引使用情况和情况二相同，因为title未提供，所以查询只用到了索引的第一列，而后面的from_date虽然也在索引中，但是由于title不存在而无法和左前缀连接，因此需要对结果进行扫描过滤from_date（这里由于emp_no唯一，所以不存在扫描）。如果想让from_date也使用索引而不是where过滤，可以增加一个辅助索引<emp_no, from_date="">，此时上面的查询会使用这个索引。除此之外，还可以使用一种称之为“隔离列”的优化方法，将emp_no与from_date之间的“坑”填上。</emp_no,></p>
<ol>
<li><p>坑列值较少的情况下，可以使用IN</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line"> EXPLAIN SELECT * FROM employees.titles</div><div class="line">WHERE emp_no='10001'</div><div class="line">AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager')</div><div class="line">AND from_date='1986-06-26';</div></pre></td></tr></table></figure>
</li>
<li><p>辅助索引</p>
</li>
</ol>
</li>
<li><p>查询条件没有指定索引第一列,由于不是最左前缀，索引这样的查询显然用不到索引</p>
</li>
<li><p>匹配某列的前缀字符串</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE 'Senior%';</div></pre></td></tr></table></figure>
<p> 如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀</p>
</li>
<li><p>范围查询</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">EXPLAIN SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer';</div></pre></td></tr></table></figure>
<p> 范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">EXPLAIN SELECT * FROM employees.titles</div><div class="line">WHERE emp_no < 10010'</div><div class="line">AND title='Senior Engineer'</div><div class="line">AND from_date BETWEEN '1986-01-01' AND '1986-12-31';</div></pre></td></tr></table></figure>
<p> 可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方，那就是<strong>仅用explain可能无法区分范围索引和多值匹配</strong>，因为在type中这两者都显示为range。同时，用了“between”并不意味着就是范围查询，例如下面的查询：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line"> EXPLAIN SELECT * FROM employees.titles</div><div class="line">WHERE emp_no BETWEEN '10001' AND '10010'</div><div class="line">AND title='Senior Engineer'</div><div class="line">AND from_date BETWEEN '1986-01-01' AND '1986-12-31';</div></pre></td></tr></table></figure>
<p> 看起来是用了两个范围查询，但作用于emp_no上的<strong>“BETWEEN”实际上相当于“IN”</strong>，也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配，否则会对MySQL的行为产生困惑。</p>
</li>
<li><p>查询条件中含有函数或表达式。<br> 如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引，例如</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line">#title 无法用到索引</div><div class="line">EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND left(title, 6)='Senior';</div><div class="line"></div><div class="line">#查询条件是一个表达式</div><div class="line">EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1='10000';</div></pre></td></tr></table></figure>
</li>
</ol>
</li>
</ol>
<h6 id="索引选择性与前缀索引"><a href="#索引选择性与前缀索引" class="headerlink" title="索引选择性与前缀索引"></a>索引选择性与前缀索引</h6><ol>
<li>索引代价：<ol>
<li>消耗存储空间（表比较少，2000条）</li>
<li>加重插入、删除和修改记录时负担</li>
<li>MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好 </li>
</ol>
</li>
<li><p>索引选择性比较低 Index Selectivity = 不重复的索引值（Cardinality）/ #T (表记录数) </p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"> # 越大越有价值</div><div class="line">SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;</div></pre></td></tr></table></figure>
</li>
<li><p>前缀索引（与索引的选择性有关 -> 索引优化策略,但是不能用于ORDER BY 和 GROUP BY） </p>
<ol>
<li><p>按名字搜索一个人</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line"># 由于没有索引，所以频繁搜索的话，效率太低</div><div class="line">employees.employees WHERE first_name='Eric' AND last_name='Anido';</div></pre></td></tr></table></figure>
</li>
<li><p>按<first_name>或<first_name,last_name>建立索引</first_name,last_name></first_name></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div></pre></td><td class="code"><pre><div class="line"> # first_name的索引选择性</div><div class="line"> SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;</div><div class="line"> # first_name, last_name的索引选择性</div><div class="line"> SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;</div><div class="line"> # 虽然first_name, last_name的索引选择性较高，但是长度为30，太长了，选择last_name的前3个字符前缀，Selectivity：0.7879</div><div class="line"> SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;</div><div class="line"> # 取前4个前缀，Selectivity：0.9007</div><div class="line"> SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;</div><div class="line"> # 加索引</div><div class="line">ALTER TABLE employees.employees</div><div class="line">ADD INDEX `first_name_last_name4` (first_name, last_name(4));</div><div class="line"> # 分析一下加索引后的性能</div><div class="line"> SHOW PROFILES;</div></pre></td></tr></table></figure>
</li>
<li><p>InnoDB的主键选择与插入优化（使用自增主键->优化层面）<br>InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。<br>如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如下图所示：<br><img src="/images/15329218696192.jpg" alt=""></p>
</li>
</ol>
</li>
</ol>
<p>这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。<br>如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：<br><img src="/images/15329218840045.jpg" alt=""></p>
<p>此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。<br>因此，<strong>只要可以，请尽量在InnoDB上采用自增字段做主键</strong>。</p>
<h5 id="查询优化"><a href="#查询优化" class="headerlink" title="查询优化"></a>查询优化</h5>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/07/30/JavaSE/常用知识积累/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="EtanWatson">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/header.png">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="EWSUN">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/07/30/JavaSE/常用知识积累/" itemprop="url">未命名</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2018-07-30T10:44:15+08:00">
2018-07-30
</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="常用知识积累"><a href="#常用知识积累" class="headerlink" title="常用知识积累"></a>常用知识积累</h1><h2 id="java虚拟机"><a href="#java虚拟机" class="headerlink" title="java虚拟机"></a>java虚拟机</h2><h3 id="JVM运行时内存区域的划分"><a href="#JVM运行时内存区域的划分" class="headerlink" title="JVM运行时内存区域的划分"></a>JVM运行时内存区域的划分</h3><ol>
<li>程序计数器：用来指示执行那条指令的</li>
<li>虚拟机栈：java栈（java方法）-栈帧 局部变量表 操作数栈 运行时常量池的引用，方法返回地址</li>
<li>本地方法栈：本地方法 HotSpot虚拟机java栈和本地方法栈合并</li>
<li>java堆：存储对象本身以及数组</li>
<li>方法区：与堆一样，是被线程共享的区域，在方法区中，存储了每个类的信息（包括累的名称，方法信息，字段信息）、静态变量、常量以及编译后的代码，运行时常量池（jdk1.7以后将其从永久代中移除）</li>
</ol>
<h3 id="java内存模型"><a href="#java内存模型" class="headerlink" title="java内存模型"></a>java内存模型</h3><p>JMM是围绕原子性，有序性、可见性展开的(稍后会分析)。JMM与Java内存区域唯一相似点，都存在共享数据区域和私有数据区域，在JMM中主内存属于共享数据区域，从某个程度上讲应该包括了堆和方法区，而工作内存数据线程私有数据区域，从某个程度上讲则应该包括程序计数器、虚拟机栈以及本地方法栈。或许在某些地方，我们可能会看见主内存被描述为堆内存，工作内存被称为线程栈</p>
<ol>
<li>主内存</li>
<li>工作内存</li>
<li><img src="/images/15329219398244.jpg" alt=""></li>
</ol>
<h4 id="java-内存模型的承诺"><a href="#java-内存模型的承诺" class="headerlink" title="java 内存模型的承诺"></a>java 内存模型的承诺</h4><ol>
<li>原子性 Synchronized和 lock</li>
<li>指令重排 volatile</li>
<li>可见性 volatile</li>
<li>happens-before原则（8条原则）</li>
</ol>
<h3 id="根可达性分析"><a href="#根可达性分析" class="headerlink" title="根可达性分析"></a>根可达性分析</h3><h4 id="如何判断对象是否可以被回收"><a href="#如何判断对象是否可以被回收" class="headerlink" title="如何判断对象是否可以被回收"></a>如何判断对象是否可以被回收</h4><p>它把内存中的每一个对象都看作一个节点，并且定义了一些对象作为根节点“GC Roots”。如果一个对象中有另一个对象的引用，那么就认为第一个对象有一条指向第二个对象的边，如下图所示。JVM会起一个线程从<strong>所有的GC Roots</strong>开始往下遍历，当遍历完之后如果发现有一些对象不可到达，那么就认为这些对象已经没有用了，需要被回收。</p>
<h4 id="作为GC-Roots的对象"><a href="#作为GC-Roots的对象" class="headerlink" title="作为GC Roots的对象"></a>作为GC Roots的对象</h4><ol>
<li>虚拟机栈中的引用的对象</li>
<li>全局的静态的对象</li>
<li>常量的引用</li>
<li>本地方法栈<h4 id="被引用的状态"><a href="#被引用的状态" class="headerlink" title="被引用的状态"></a>被引用的状态</h4></li>
<li>强引用</li>
<li>软引用：内存濒临溢出</li>
<li>弱引用：一次gc就会被回收</li>
<li>虚引用：</li>
</ol>
<h4 id="常见的GC回收算法及其含义"><a href="#常见的GC回收算法及其含义" class="headerlink" title="常见的GC回收算法及其含义"></a>常见的GC回收算法及其含义</h4><ol>
<li>标记-清除算法：内存碎片化</li>
<li>复制算法：（java对堆中新生代的垃圾回收算法）损失掉部分系统内存</li>
<li>标记-整理（java堆中老年代的垃圾回收算法）</li>
</ol>
<h4 id="G1与CMS"><a href="#G1与CMS" class="headerlink" title="G1与CMS"></a>G1与CMS</h4><ol>
<li><p>CMS收集器是一种以获取最短回收停顿时间为目标的收集器，基于“标记-清除”算法实现</p>
<ol>
<li>初始标记：stop the word</li>
<li>并发标记</li>
<li>重新标记</li>
<li><p>并发清除</p>
<p>优点：并发收集，停顿低<br>缺点：1）CMS收集器对CPU资源非常敏感，用户线程停顿<br> 2）CMS无法处理浮动垃圾<br> 3）大量空间碎片</p>
</li>
</ol>
</li>
<li><p>G1收集器</p>
<ol>
<li>并行与并发：</li>
<li>分代收集</li>
<li>空间整理</li>
<li><p>可预测的停顿</p>
<p>G1运作步骤： 1 初始标记、 2 并发标记、 3 最终标记 、4 筛选回收</p>
<h4 id="如何确保新生代对象被老年代对象引用的时候不被gc"><a href="#如何确保新生代对象被老年代对象引用的时候不被gc" class="headerlink" title="如何确保新生代对象被老年代对象引用的时候不被gc"></a>如何确保新生代对象被老年代对象引用的时候不被gc</h4><p>机制：当老年代存活对象多时，每次minor gc查询老年代所有对象邮箱gc效率，card table</p>
</li>
</ol>
</li>
</ol>
<h3 id="类加载机制"><a href="#类加载机制" class="headerlink" title="类加载机制"></a>类加载机制</h3><h4 id="类加载器：启动类加载器-rt-jar、标准扩展类加载器-lib-ext、系统类加载器-classPath"><a href="#类加载器：启动类加载器-rt-jar、标准扩展类加载器-lib-ext、系统类加载器-classPath" class="headerlink" title="类加载器：启动类加载器 rt.jar、标准扩展类加载器 /lib/ext、系统类加载器 classPath"></a>类加载器：启动类加载器 rt.jar、标准扩展类加载器 <java_home>/lib/ext、系统类加载器 classPath</java_home></h4><p><img src="/images/15329219586535.jpg" alt=""></p>
<h5 id="委托机制"><a href="#委托机制" class="headerlink" title="委托机制"></a>委托机制</h5><h5 id="全盘负责"><a href="#全盘负责" class="headerlink" title="全盘负责"></a>全盘负责</h5><h2 id="多线程"><a href="#多线程" class="headerlink" title="多线程"></a>多线程</h2><h3 id="volatile"><a href="#volatile" class="headerlink" title="volatile"></a>volatile</h3><p>使用violatile修饰的变量在汇编阶段，会多出一条lock前缀指令，它在多核处理器下会引发两件事情</p>
<ol>
<li>将当前处理器缓存行的数据写会到系统内存</li>
<li>这个写会内存的操作会使在其他cpu里缓存了该内存地址无效</li>
</ol>
<h3 id="Synchronized和lock"><a href="#Synchronized和lock" class="headerlink" title="Synchronized和lock"></a>Synchronized和lock</h3><h4 id="synchronized（对象监视器-monitorenter-monitorexit，一个线程进入临界区、内存可见性）"><a href="#synchronized（对象监视器-monitorenter-monitorexit，一个线程进入临界区、内存可见性）" class="headerlink" title="synchronized（对象监视器 monitorenter monitorexit，一个线程进入临界区、内存可见性）"></a>synchronized（对象监视器 monitorenter monitorexit，一个线程进入临界区、内存可见性）</h4><ol>
<li>普通同步方法，锁是当前实例对象</li>
<li>静态同步方法，锁是当前类的class对象</li>
<li>同步方法块，锁是括号里的对象</li>
</ol>
<h4 id="和lock的区别"><a href="#和lock的区别" class="headerlink" title="和lock的区别"></a>和lock的区别</h4><ol>
<li>关键字</li>
<li>锁状态</li>
<li>是否自动释放锁</li>
<li>是否可中断，可公平</li>
<li>是否需要一直等待</li>
<li>代码量的大小</li>
</ol>
<h3 id="AQS同步队列"><a href="#AQS同步队列" class="headerlink" title="AQS同步队列"></a>AQS同步队列</h3><p>volatile int state<br>FIFO线程等待队列</p>
<h3 id="CAS无锁概念（ABA问题）"><a href="#CAS无锁概念（ABA问题）" class="headerlink" title="CAS无锁概念（ABA问题）"></a>CAS无锁概念（ABA问题）</h3><p>V 要更新的值<br>E 预期的值<br>N 表示新值</p>
<h3 id="悲观锁与乐观锁"><a href="#悲观锁与乐观锁" class="headerlink" title="悲观锁与乐观锁"></a>悲观锁与乐观锁</h3><p>1、保守态度<br>2、积极态度，别人不会修改</p>
<h3 id="锁类型"><a href="#锁类型" class="headerlink" title="锁类型"></a>锁类型</h3><ol>
<li>自旋锁 cpu空转</li>
<li>偏向锁 当有其他线程竞争的时候，会升级成轻量级锁</li>
</ol>
<h3 id="线程池"><a href="#线程池" class="headerlink" title="线程池"></a>线程池</h3><h4 id="ThreadPoolExecutor"><a href="#ThreadPoolExecutor" class="headerlink" title="ThreadPoolExecutor"></a>ThreadPoolExecutor</h4><p>corePoolSize（线程池的基本大小）<br>runnableTaskQueue（任务队列）保存等待执行任务的阻塞队列<br>maximumPoolSize(线程池最大大小)：线程池永续创建的最大线程数<br>RejectedExecutionHandler(饱和策略) </p>
<h4 id="newCachedThreadPool（创建一个可缓存线程池）"><a href="#newCachedThreadPool（创建一个可缓存线程池）" class="headerlink" title="newCachedThreadPool（创建一个可缓存线程池）"></a>newCachedThreadPool（创建一个可缓存线程池）</h4><h4 id="newFixedThreadPool（创建一个指定工作线程数量的线程池）"><a href="#newFixedThreadPool（创建一个指定工作线程数量的线程池）" class="headerlink" title="newFixedThreadPool（创建一个指定工作线程数量的线程池）"></a>newFixedThreadPool（创建一个指定工作线程数量的线程池）</h4><h4 id="newSingleThreadExecutor（创建一个单线程化的Executor）"><a href="#newSingleThreadExecutor（创建一个单线程化的Executor）" class="headerlink" title="newSingleThreadExecutor（创建一个单线程化的Executor）"></a>newSingleThreadExecutor（创建一个单线程化的Executor）</h4><h4 id="newScheduleThreadPool（创建一个定长的线程池，而且支持定时以及周期性任务执行）"><a href="#newScheduleThreadPool（创建一个定长的线程池，而且支持定时以及周期性任务执行）" class="headerlink" title="newScheduleThreadPool（创建一个定长的线程池，而且支持定时以及周期性任务执行）"></a>newScheduleThreadPool（创建一个定长的线程池，而且支持定时以及周期性任务执行）</h4><h2 id="计算机网络"><a href="#计算机网络" class="headerlink" title="计算机网络"></a>计算机网络</h2><h3 id="3次握手和4次挥手"><a href="#3次握手和4次挥手" class="headerlink" title="3次握手和4次挥手"></a>3次握手和4次挥手</h3><p><img src="/images/15329219759485.jpg" alt=""></p>
<ol>
<li>3次握手<br>小明拨打小红的电话<br>小红按下通话键并说了声，喂 （一次握手）<br>小明听到小红的回应，也说了声，喂 （二次握手）<br>小红接收到小明的回应 （三次握手）</li>
<li>4次挥手<br>小明：我这没事儿了，你还有事儿吗？ （1次挥手）<br>小红：我也没事儿了，你确定没事儿了吗？ （2次挥手）<br>小红：我要挂电话了。 （3次挥手）<br>小明：好吧，你挂吧。 （4次挥手）</li>
</ol>
<h3 id="http与https的区别"><a href="#http与https的区别" class="headerlink" title="http与https的区别"></a>http与https的区别</h3><p>HTTP协议传输的数据都是未加密的，也就是明文的，因此使用HTTP协议传输隐私信息非常不安全，为了保证这些隐私数据能加密传输，于是网景公司设计了SSL（Secure Sockets Layer）协议用于对HTTP协议传输的数据进行加密，从而就诞生了HTTPS。简单来说，HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，要比http协议安全。</p>
<h3 id="一次HTTP请求的完整过程"><a href="#一次HTTP请求的完整过程" class="headerlink" title="一次HTTP请求的完整过程"></a>一次HTTP请求的完整过程</h3><h4 id="请求格式-请求行、请求头、空行、消息体"><a href="#请求格式-请求行、请求头、空行、消息体" class="headerlink" title="请求格式 请求行、请求头、空行、消息体"></a>请求格式 请求行、请求头、空行、消息体</h4><h4 id="相应格式-状态行、响应头、空行-、消息体"><a href="#相应格式-状态行、响应头、空行-、消息体" class="headerlink" title="相应格式 状态行、响应头、空行 、消息体"></a>相应格式 状态行、响应头、空行 、消息体</h4><h4 id="完整过程"><a href="#完整过程" class="headerlink" title="完整过程"></a>完整过程</h4><ol>
<li>域名解析（浏览器-> 系统 -> hosts文件 ->首选DNS服务器）</li>
<li>发起TCP的3次握手</li>
<li>建立tcp连接后发起的http请求</li>
<li>服务端相应http请求，浏览器得到html代码</li>
<li>浏览器渲染</li>
</ol>
<h2 id="java集合类相关"><a href="#java集合类相关" class="headerlink" title="java集合类相关"></a>java集合类相关</h2><h3 id="List和Set"><a href="#List和Set" class="headerlink" title="List和Set"></a>List和Set</h3><p>List：重复，多个null元素，有序（ArrayList，LinkedList，Vector）<br>Set：不重复、无序（TreeSet->Comparable） HashSet(基于HashMap)<br>Map： Map 键（不同，最多一个null） 值（可以相同，可以拥有多个null）</p>
<h3 id="ArrayList与LinkedList的区别于优势"><a href="#ArrayList与LinkedList的区别于优势" class="headerlink" title="ArrayList与LinkedList的区别于优势"></a>ArrayList与LinkedList的区别于优势</h3><h4 id="ArrayList"><a href="#ArrayList" class="headerlink" title="ArrayList"></a>ArrayList</h4><ol>
<li>基于动态数组的数据结构</li>
<li>随机访问<h4 id="LinkedList"><a href="#LinkedList" class="headerlink" title="LinkedList"></a>LinkedList</h4></li>
<li>基于链表的数据结构</li>
<li>新增和删除</li>
</ol>
<h3 id="HashMap与ConcurrentHashMap"><a href="#HashMap与ConcurrentHashMap" class="headerlink" title="HashMap与ConcurrentHashMap"></a>HashMap与ConcurrentHashMap</h3><p>HashMap是线程不安全的，在并发环境下，可能会形成环状链表（扩容时造成），导致get操作时，cpu空转<br>HasTable性能差的主要是由于所有操作需要竞争同一把锁，而如果容器中有多把锁，每一把锁锁一段数据，这样多线程访问是不同段的数据时，就不会存在锁竞争了，“分段锁”<br>get方法无需加锁，他是volatile变量，内存可见性<br>count</p>
<p>hashMap初始大小是16，扩容因子默认是0.75<br>ArrayList初始化大小是10，扩容规则的大小=原始大小+原始大小/2+1</p>
<h2 id="算法与数据结构"><a href="#算法与数据结构" class="headerlink" title="算法与数据结构"></a>算法与数据结构</h2><h3 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div></pre></td><td class="code"><pre><div class="line">private static void quickSort(int[] a, int low, int height){</div><div class="line"> // 出口</div><div class="line"> if(low > height){</div><div class="line"> return;</div><div class="line"> }</div><div class="line"> // 存</div><div class="line"> int i = low;</div><div class="line"> int j = high;</div><div class="line"> // key</div><div class="line"> int key = a[low];</div><div class="line"> // 完成一趟排序</div><div class="line"> while(i < j){</div><div class="line"> while(i < j && a[j] > key){</div><div class="line"> j --;</div><div class="line"> }</div><div class="line"> while(i < j && a[i] <= key){</div><div class="line"> i++;</div><div class="line"> }</div><div class="line"> // 交换</div><div class="line"> if(i < j){</div><div class="line"> int tmp = a[i];</div><div class="line"> a[i] = a[j];</div><div class="line"> a[j] = tmp;</div><div class="line"> }</div><div class="line"> }</div><div class="line"> </div><div class="line"> // 调整key的位置 ???有误</div><div class="line"> int p = a[i];</div><div class="line"> a[i] = a[low];</div><div class="line"> a[low] = p;</div><div class="line"> </div><div class="line">}</div></pre></td></tr></table></figure>
<h2 id="其他题目"><a href="#其他题目" class="headerlink" title="其他题目"></a>其他题目</h2><h3 id="t1，t2，t3顺序执行"><a href="#t1，t2，t3顺序执行" class="headerlink" title="t1，t2，t3顺序执行"></a>t1，t2，t3顺序执行</h3><p>join()</p>
<h3 id="JMM"><a href="#JMM" class="headerlink" title="JMM"></a>JMM</h3><h3 id="http请求的一个过程"><a href="#http请求的一个过程" class="headerlink" title="http请求的一个过程"></a>http请求的一个过程</h3><h3 id="内存分析工具"><a href="#内存分析工具" class="headerlink" title="内存分析工具"></a>内存分析工具</h3><h3 id="缓存插件"><a href="#缓存插件" class="headerlink" title="缓存插件"></a>缓存插件</h3><h3 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h3><h3 id="concurrent包"><a href="#concurrent包" class="headerlink" title="concurrent包"></a>concurrent包</h3><ol>
<li>locks部分：显式锁</li>
<li>atomic部分：原子变量类</li>
<li>executor部分：线程池相关</li>
<li>collections部分：并发容器相关</li>
<li>tools部分：同步工具相关，如信号量</li>
</ol>
<p>ConcurrentHashMap与HashTable比较</p>
<ol>
<li>更好的并发性能，不会把整个Map锁住，只是把Map中正在被写入的部分进行锁定</li>
<li>在遍历的时候，即使ConcurrentHashMap被改动，它也不会抛出ConcurrentModificationException</li>
</ol>
<p>CountDownLatch 与 CyclicBarrier</p>
<ol>
<li>减计数方式 - 加计数方式</li>
</ol>
<p>Exchanger原理<br>提供的是一个交换服务，允许原子性的交换两个（多个）对象，但是同时只有一对才能成功</p>
<p>Semaphore 信号量</p>
<ol>
<li>保护一个重要（代码）部分防止一次超过N个线程进入</li>
<li>在两个线程之间发送信号</li>
</ol>
<h3 id="IOC"><a href="#IOC" class="headerlink" title="IOC"></a>IOC</h3><h3 id="AOC"><a href="#AOC" class="headerlink" title="AOC"></a>AOC</h3><h3 id="单例模式（单例）"><a href="#单例模式（单例）" class="headerlink" title="单例模式（单例）"></a>单例模式（单例）</h3><h3 id="设计模式"><a href="#设计模式" class="headerlink" title="设计模式"></a>设计模式</h3><h3 id="Spring事务传播机制"><a href="#Spring事务传播机制" class="headerlink" title="Spring事务传播机制"></a>Spring事务传播机制</h3><h3 id="redis"><a href="#redis" class="headerlink" title="redis"></a>redis</h3><h4 id="Redis单线程"><a href="#Redis单线程" class="headerlink" title="Redis单线程"></a>Redis单线程</h4><p>网络请求的单线程，即一个线程处理所有的网络请求</p>
<h4 id="为什么Redis能够快速执行"><a href="#为什么Redis能够快速执行" class="headerlink" title="为什么Redis能够快速执行"></a>为什么Redis能够快速执行</h4><ol>
<li>内存操作</li>
<li>单线程，避免了不必要的上下文切换和竞争条件</li>
<li>非阻塞IO - 多路复用IO</li>
</ol>
<h4 id="Redis线程安全问题"><a href="#Redis线程安全问题" class="headerlink" title="Redis线程安全问题"></a>Redis线程安全问题</h4><ol>
<li>线程封闭的观念</li>
<li>依赖多个redis复合操作来说，依然需要锁</li>
</ol>
<h4 id="Redis两种持久化方法的优缺点"><a href="#Redis两种持久化方法的优缺点" class="headerlink" title="Redis两种持久化方法的优缺点"></a>Redis两种持久化方法的优缺点</h4><p>RDB：指定的时间间隔内生成数据集的时间点快照<br>AOF：记录所有写操作命令</p>
<h4 id="Redis常见的5中不同的数据类型详解"><a href="#Redis常见的5中不同的数据类型详解" class="headerlink" title="Redis常见的5中不同的数据类型详解"></a>Redis常见的5中不同的数据类型详解</h4><p>String字符串<br>List链表<br>Set集合<br>Hash散列<br>ZSet有序集合</p>
<h3 id="列表-堆栈-数组"><a href="#列表-堆栈-数组" class="headerlink" title="列表 堆栈 数组"></a>列表 堆栈 数组</h3>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/06/05/Hadoop相关/scala/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="EtanWatson">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/header.png">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="EWSUN">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/06/05/Hadoop相关/scala/" itemprop="url">scala</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2018-06-05T12:28:29+08:00">
2018-06-05
</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/Hadoop相关/" itemprop="url" rel="index">
<span itemprop="name">Hadoop相关</span>
</a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="scala"><a href="#scala" class="headerlink" title="scala"></a>scala</h1><blockquote>
<p>由于gethub托管的太慢的原因，现在准备将blog部署到阿里云上面，所以有都没有写完</p>
</blockquote>
<h3 id="函数和方法的最大区别"><a href="#函数和方法的最大区别" class="headerlink" title="函数和方法的最大区别"></a>函数和方法的最大区别</h3><blockquote>
<p>函数可以当做参数传入方法中</p>
</blockquote>
<h3 id="map"><a href="#map" class="headerlink" title="map()"></a>map()</h3><blockquote>
<p>可以用自定义函数处理相关集合 map(_+10) //里面传的是匿名函数<br>map((x: Int) => x * 100)</p>
</blockquote>
<h3 id="神奇的下划线"><a href="#神奇的下划线" class="headerlink" title="神奇的下划线"></a>神奇的下划线</h3><h4 id="将方法转换成函数"><a href="#将方法转换成函数" class="headerlink" title="将方法转换成函数"></a>将方法转换成函数</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">var f2 = m2 _</div></pre></td></tr></table></figure>
<h3 id="相关函数"><a href="#相关函数" class="headerlink" title="相关函数"></a>相关函数</h3><h4 id="reduce"><a href="#reduce" class="headerlink" title="reduce()"></a>reduce()</h4><h4 id="fold"><a href="#fold" class="headerlink" title="fold()"></a>fold()</h4><h5 id="foldLeft"><a href="#foldLeft" class="headerlink" title="foldLeft()"></a>foldLeft()</h5><h4 id="a-par-并行计算"><a href="#a-par-并行计算" class="headerlink" title="a.par (并行计算)"></a>a.par (并行计算)</h4>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/06/02/JavaSE/流/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="EtanWatson">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/header.png">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="EWSUN">
</span>
<header class="post-header">