没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

线性排序

常见的三种以线性时间运行的算法：计数排序、基数排序和桶排序；网上教程不少，但三者经常混淆，称桶排序但实质可能是计数排序，为了保证原味性，主要参考《算法导论》

需要注意的是线性排序算法是非基于比较的排序算法，都有使用限制才能达到线性排序的效果

定义

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））

算法

桶排序的思想：其实就是先分配再收集的这个一个过程

假设输入是一个随机过程产生的[0,1)区间上均匀分布的实数

把区间划分成n个大小相同的子区间，或称为桶。然后将n个输入元素分布的各个桶中去。先对各个桶中的数进行排序，然后按次序把各桶中的数据列出来即可

（因为输入元素均匀而独立的分布在区间 [0,1)上，所以不会出现很多数落在一个桶中的情况）

在桶排序算法中，假设输入的是一个含n个元素的数组A，且每个元素满足0≤A[i]<1。另外，还需要一个辅助数组B[0…n-1]来存放链表（桶），并假设可以用某种机制来维护这些表

【刚开始按照示例图的方式理解了桶排序，桶分10个，以十分位为桶号放入各个桶，也算是桶排序一种实现方式，但还是狭隘了】

在实际应用时，其实并不然必须元素范围为[0,1)，整数，小数都是可以的，只要分布均匀就能最大发挥桶排序优势

优质的桶排序需要考虑几个因素：

1. 桶的数量：桶越多，占用空间越大
2. 区间跨度：桶与桶之间的跨度
3. 桶内元素的排序

一般区间跨度：

除了最后一个桶只包含一个最大值之外，其余各桶之间的区间跨度=(最大值-最小值)/(桶数量-1)

1
2
3
4
5
6
7
8

//伪代码
BUCKET_SORT(A)  
n = length(A)   
for i= 1 to n       
    do insert A[i] into list B   
 for i=0 to n-1       
    do sort list B[i] with insertion sort
 concatenate the list B[0]、B[1]，，，B[n-1] together in order

实现

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

private static void bucketSort(double [] array){
	int bucketNum = 10;//10个桶
	double max = Double.MIN_VALUE;
	double min = Double.MIN_VALUE;
	for (double a:array) {
		if(a> max) {
			max = a;
		}
		if(a<min) {
			min = a;
		}
	}
	//区间跨度
	double span  = (max - min) / (bucketNum - 1);
	double [][]buckets = new double[bucketNum][];
	//初始化桶
	for (int b = 0; b<bucketNum;b++) {
		//以排序元素个数初始化每个桶，以防极端情况
		buckets[b] = new double[array.length];
	}
	//每个桶的元素数量
	int [] index = new int[10];
	for (int d = 0;d<array.length;d++) {
		int bucket =  (int)((array[d] - min)/span);
		buckets[bucket][index[bucket]] = array[d];
		index[bucket]++;
	}

	//每个桶排序，直接使用sort函数了
	for(int b = 0; b<10; b++) {
		Arrays.sort(buckets[b]);
	}
	int j = 0;
	for(int b = 0; b<10; b++) {
		if(index[b] == 0) {
			continue;
		}
		//这儿需要特殊处理一下，主要是因为每个桶初始化了array.length，
		// 经过sort排序，比如第一个桶数组变成了[0.0,0.0,......0.002]
		//需要剔掉数组中的0
		for (int bi = array.length-index[b];bi<array.length;bi++) {
			array[j++] = buckets[b][bi];
		}
	}
}

复杂度

时间复杂度：

假设有m个桶，则每个桶的元素为n/m;

当辅助函数为冒泡排序O(n^2)时,桶排序为 O(n)+mO((n/m)2);

当辅助函数为快速排序时O(nlgn)时,桶排序为 O(n)+m*O(n/m log(n/m))

空间复杂度：　

O(M+N)

通常桶越多，执行效率越快，即省时间，但是桶越多，空间消耗就越大，是一种通过空间换时间的方式

之前这本书翻译为《营销战》，现在又翻译成《商战》了

结合当前商业动态，此书可能会回答你心中的一些问题

为什么哈罗单车融资成功了，可ofo压金都成了问题？
为什么在阿里绝对的市场占有率之机，拼多多诞生了并还在持续增长？
当年的当当图书，京东快递如何抢占了客户
真的是打江山容易，守江山难吗？
战略与战术到底哪一个更重要？

商业即战争

战争属于商业竞争的范畴，同样也是人类利益和活动的冲突

商业需要新理念

明确清晰的定义是重要的开始，定义就是角度，也见深度

1. 商业活动必须满足消费者的需要和需求
2. 人类通过交换过程满足需要和需求的活动
3. 引导商品和服务从生产者流向消费者的一系列经济活动
4. 通过预测顾客或客户需求，并引导满足需求的商品和服务从生产者流向顾客或客户，从而实现组织目标的各种活动
5. 确定客户需求、根据组织生产能力将需求概念化、将概念同组织的适当能力相联系、根据先前确定的客户需求，使随后的生产概念化、将此概念同客户相联系

兵力原则

基本原则：兵力优势。无论何时，都应该首先尽力做到这一点

用兵之法，十则围之，五则攻之，倍则战之，敌则能分之，少则能逃之，不若则能避之。故小敌之坚，大敌之擒也

兵力原则是最基本的战争原则，其本质就是以多打少：大鱼吃小鱼，大公司击败小公司

战地性质

商战在心智中打响，它无时无刻不存在于你自己和潜在顾客的心智中。

心智即战场，一个复杂且难以理解的阵地

战略形式

防御战

原则

1. 只有市场领导者才能打防御战

2. 最佳的防御就是勇于自我攻击

3. 强大进攻必须及时封杀

进攻战

领导者应进行防御战，而非攻击战

进攻战适用于行业第二或第三的公司，公司要足够强大才能向领导者发起持续进攻

原则

1. 领导者的强势地位是主要的考虑因素
2. 找到领导者强势中的弱势，并聚而攻之
3. 尽可能在狭长地带发起攻击

侧翼战

侧翼战是最具有创新性的战略形式

原则

1. 最佳的侧翼战是在无争地带展开

2. 战术奇袭是作战计划中最重要的一环

3. 追击与进攻同等重要

游击战

敌进我退，敌驻我拢，敌疲我打，敌退我追

原则

1. 找到一块小得足以守得住的阵地

2. 无论多么成功，都不能效仿领导者

3. 一旦有变，随时准备撤退

VS侧翼战

战略与战术

“战术驱动战略”，这是战争研究得出的最重要思想之一。

战略服从战术就像形式服从内容一样，战略应该服从战术。战术结果的取得，是战略的最终目标和唯一目的。

伟大的战略目标是使一切工作在一定的战术层面上顺利进行，而不是其他什么目的

巴顿说：“人们不应该先制订计划，然后让形势适应计划，而应该让计划适应当前的形势。我认为，胜败取决于最高指挥部是否拥有这种能力。”

总结

可以尝试性的给开篇的问题给个答案，不一定对，毕竟不是专业人士，也非局中之人

当年共享单车红遍南北，貌似市场被ofo，魔拜一统天下；而一些品牌却玩起了游击战，突袭攫取他们放弃的三四线城市，并快速追击，以致当领导者出现疲态时，主动进攻，一举进入了一线城市

一个品牌无法支撑两个不同的概念。低价劳斯莱斯会损害其高价的定位，而且很多时候，低价产品无法热销，因为没有人愿意购买廉价的劳斯莱斯。

所以阿里有了淘宝，也要搞天猫；但不可能一统所以市场，拼多多抓住了被忽略，或者说是阿里主动放弃的领地，提出社交电商，打了一个漂亮的侧翼战

淘宝火及一时，可为什么选择京东购物？淘宝品种很全，但物流不够快，京东发现了客户痛点，找到了淘宝领导者强势中的弱势，以“隔日达”为口号，快速占领了用户心智

战略重要，还是战术重要的呢？ 好似道与术的取舍一样。人们总认为道更重要。与IT行业的架构一样

但康威定律如是说：设计系统的组织，其产生的设计等同于组织之内、组织之间的沟通结构。也就是架构偏向于组织结构，如果架构异于组织结构，那可能再完美的架构也无法落地。无法落地的架构是好架构吗？

一个伟大的战略必须要以当前环境的战术能力为前提，不能实现，能算是好战略吗？

树的类型不少，此篇简要对树进行描述，脑中有个整体概念，细节分篇再研究

树

树（Tree）是n（n>=0）个结点的有限集。

在任意一棵非空树中：

（1）有且仅有一个特定的称为根（Root）的结点；

（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2，…，Tn，其中每个集合本身又是一棵树，并称为根的子树（SubTree）

术语

1. 结点：如上图，每一个圈圈我们就称为树的一个结点
2. 度: 结点拥有的子树数称为结点的度-(Degree)，树的度取树内各结点的度的最大值
3. 叶结点(Leaf)或终端结点: 度为0的结点
4. 内部结点: 度不为0的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点。5. 结点间的关系：结点的子树的根称为结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)，同一双亲的孩子之间互称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点
5. 深度：树中结点的最大层次称为树的深度(Depth)或高度
6. 结点的层次(Level): 从根开始定一起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟
7. 有序树: 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树, 否则为无序树
8. 森林(Forest): 是 m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林

二叉树

二叉树(Binary Tree)是n(n>=0)个结点的有限集合。该集合可能是空的（空二叉树），也可能由
一个根结点和该根结点的左子树和右子树组成。左右子树不相交，而且都是二叉树

特点

1. 每个结点最多有两棵字树，即每个结点的度和树的度不大于2。
2. 结点的左子树和右子树是有顺序的，不能颠倒。
3. 即使结点只有一棵子树，也是有顺序的

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上

完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树

之前讲过的《堆排序》 就是依赖完全二叉树结构

二叉查找树

二叉查找树(Binary Search Tree)，又被称为二叉搜索树

（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2） 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3） 任意节点的左、右子树也分别为二叉查找树；

（4） 没有键值相等的节点

复杂度

复杂度分析：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡

平衡二叉树

平衡二叉搜索树，又被称为AVL树

由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，所以，这也是平衡二叉树设计的初衷。

具有以下性质：

1. 要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；
2. 其左右子树也都是平衡二叉树；
3. 二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1

红黑树

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为”对称二叉B树”，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目

特性

1. 每个节点要么是红色，要么是黑色。
2. 根节点永远是黑色的。
3. 所有的叶节点都是空节点（即 null），并且是黑色的。
4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

为什么需要红黑树

平衡二叉树的插入/删除操作带来的旋转操作可能会达到logn次

红黑树的插入操作最多进行两次旋转、删除操作最多进行三次旋转

B树

B树是一种平衡的多路查找树，结点最大的孩子数目称为B树的阶（Order），是为磁盘存储而专门设计的一类平衡搜索树

b-tree分为用“阶”的定义和用“度”的定义，度和阶都是描述子节点的数量的

特性

1. 定义任意非叶子结点最多只有M个儿子；且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子结点位于同一层；

这是B树存储在硬盘的逻辑结构图。

其中根节点中17，35在称为关键字(key) ，实际中往往附带更多复杂类型数据。

可以看出一个节点包含 keys ChildNotePointer 2部分信息

为什么需要B树

1. 当数据量大的时候，树的高度会比较高，数据量大的时候，查询会比较慢
2. 树每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO

这是个典型的b树结构，初始因子为1000，高度仅为3的b树，就可以存储1002001000的数据了

假设要查询最后一个数据:

• 从硬盘加载根节点搜索，IO一次。
• 根据根节点的指针信息，去加载第二层的节点， IO一次。
• 重复2，IO一次。
  IO只用了3次，就查询了需要的数据，所以说B树效率是非常高的。

B树的节点，在硬盘里表现为：柱面里的页(page)或盘块(block)，如果把索引持久化到内存，只需要一次就够了

B+树

B+树是B-树的变体，也是一种多路搜索树：

1. 其定义基本与B-树相同
2. 非叶子结点的子树指针与关键字个数相同（B树中是k-1个元素）
3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
4. 为所有叶子结点增加一个链指针
5. 所有关键字都在叶子结点出现

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找

B树：有序数组+平衡多叉树

B+树：有序数组链表+平衡多叉树

B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据

为什么需要B+树

1. b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
2. b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
3. 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历

B*树

B*树是对B+树进行的又一次的升级。在B+树的非根和非叶子结点再增加指向兄弟的指针

在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

在这比如说当你进行插入节点的时候，它首先是放到兄弟节点里面。如果兄弟节点满了的话，进行分裂的时候从兄弟节点和这个节点各取出1/3，放入新建的节点当中，这样也就实现了空间利用率从1/2到1/3。

总结

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

参考资料

B-树学习笔记

前言

索引，一种强大的存在；不管是什么行业，数据都是根基，终将落盘固化，提供各方检索查询，之前整理了一篇《深入浅出spring事务》，你可以推脱不使用事务，但索引是不可或缺的必备知识点

知识点比较多，有些会分篇细化，整体会从以下几方面整理

1. 索引是什么,人人都在讲，但他的定义到底是什么？
2. 索引作用，创建表时，都要考虑索引，能带什么好处？
3. 索引负作用，索引那么好，为什么不在每个字段上都加上索引？
4. 索引实现原理，那么多数据结构，索引为什么非要使用B+Tree？
5. 索引应用，加了索引也不一定能发挥作用，使用时注意哪些？

索引是什么

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。

最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法

例如二分查找（binary search）、二叉树查找（binary tree search）等。

如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上

例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织）

所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引

索引意义

通过索引定义，作用基本已经明确，再细化一下

作用

1. 大大加快数据的检索速度;
2. 创建唯一性索引，保证数据库表中每一行数据的唯一性;
3. 加速表和表之间的连接;
4. 在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间

反作用

索引有这么多的好处，哪是不是每一列都给建上索引相当好呢？

过犹不及

1. 索引需要占用数据表以外的物理存储空间
2. 创建索引和维护索引要花费一定的时间
3. 当对表进行更新操作时，索引需要被重建，这样降低了数据的维护速度

索引分类

分类有两种角度：

• 1.物理存储

  • 1.1 聚簇索引(Clustered Index)：将数据存储与索引放到了一块，找到索引也就找到了数据，一个表只能有一个聚集索引
  • 1.2 非聚簇索引(Non- Clustered Index)：将数据存储于索引分开结构，搜索索引，然后通过索引找到磁盘相应数据

• 2.逻辑功能

  • 2.1.主键索引：它是一种特殊的唯一索引，不允许有空值

    1	primary key (id)

  • 2.2. 普通索引：这是最基本的索引，它没有任何限制

    1	create index idx_name on user(name(20));

  • 2.3. 唯一索引：它与前面的普通索引类似，不同的就是：索引列的值必须唯一，但允许有空值

    1	CREATE UNIQUE INDEX idx_email ON user(email);

  • 2.4. 组合索引

    1	INDEX name (last_name,first_name)

Innodb使用的是聚簇索引，MyISam使用的是非聚簇索引

Innodb中的主键索引是一种聚簇索引，非聚簇索引都是辅助索引，像复合索引、前缀索引、唯一索引

在Innodb中，Mysql中的数据是按照主键的顺序来存放的。那么聚簇索引就是按照每张表的主键来构造一颗B+树，叶子节点存放的就是整张表的行数据。由于表里的数据只能按照一颗B+树排序，因此一张表只能有一个聚簇索引

在Innodb中，聚簇索引默认就是主键索引

索引实现

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数

存储原理

在了解索引的数据结构之前了解一下硬件存储原理，毕竟一切都是基于硬件

计算机存储设备一般分为两种：内存储器(main memory)和外存储器(external memory)

• 内存存取速度快，但容量小，价格昂贵，而且不能长期保存数据(在不通电情况下数据会消失)。
• 外存储器—磁盘是一种直接存取的存储设备(DASD)。它是以存取时间变化不大为特征的。可以直接存取任何字符组，且容量大、速度较其它外存设备更快。

磁盘结构

如上图，磁盘由盘片构成,每个盘片有两面，又称为盘面(Surface)，这些盘面覆盖有磁性材料。

盘片中央有一个可以旋转的主轴(spindle)，他使得盘片以固定的旋转速率旋转，通常是5400转每分钟(Revolution Per Minute,RPM)或者是7200RPM

磁盘包含一个多个这样的盘片并封装在一个密封的容器内。

上图左，展示了一个典型的磁盘表面结构。每个表面是由一组成为磁道(track)的同心圆组成的，每个磁道被划分为了一组扇区(sector).每个扇区包含相等数量的数据位，通常是（512）子节。

扇区之间由一些间隔(gap)隔开,不存储数据。

磁盘读写

如上图，磁盘用读/写头来读写存储在磁性表面的位，而读写头连接到一个传动臂的一端

磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块)

读/写磁盘上某一指定数据需要下面3个步骤：

1. 首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称为定位或查找 。
2. 所有磁头都定位到第10盘面的10条磁道上(磁头都是双向的)。这时根据盘面号来确定指定盘面上的磁道。
3. 盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下

经过上面三个步骤，指定数据的存储位置就被找到。这时就可以开始读/写操作了。
访问某一具体信息，由3部分时间组成：

• 查找时间(seek time) Ts: 完成上述步骤(1)所需要的时间。这部分时间代价最高，最大可达到0.1s左右。
• 等待时间(latency time) Tl: 完成上述步骤(3)所需要的时间。由于盘片绕主轴旋转速度很快，一般为7200转/分(电脑硬盘的性能指标之一, 家用的普通硬盘的转速一般有5400rpm(笔记本)、7200rpm几种)。因此一般旋转一圈大约0.0083s。
• 传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间，一般传输一个字节(byte)大概0.02us=2*10^(-8)s

磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上

因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间Ts

在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块(block)中某数据时，首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。

当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行

数据结构

根据索引定义，索引就是一种数据结构，来看下此数据结构是什么样的，能在当前硬件条件下，高效地查找磁盘数据,这种数据结构需要满足两个条件：

1. 快速，快速查找到数据
2. 局部性原理，满足局部性原理，减小IO次数，减小硬件磁头移动

根据之前温习的各种算法，可以找一种适合的查找算法与数据结构吗？

• 1.顺序查找：这种复杂度为O(n)的算法在数据量很大时显然是糟糕的
• 2.数组+二分查找：效率是O(logn),但是数组的插入元素以及删除元素的效率很低

• 3.hash:检索效率非常高，索引的检索可以一次定位,在Hashmap源码解析中有过详细分析

  • 3.1Hash 索引仅仅能满足”=”,”IN”和”<=>”查询，不能使用范围查询

    由于 Hash 索引比较的是进行 Hash 运算之后的 Hash值，
    所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样

  • 3.2Hash 索引无法被用来避免数据的排序操作

    由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算

  • 3.3Hash索引不能利用部分索引键查询

    对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用

  • 3.4Hash索引在任何时候都不能避免表扫描

    Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果

  • 3.5Hash索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高

    对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下

在mysql中，只有memory引擎显式支持哈希索引，这也是memory引擎表的默认索引类型，memory也支持btree，值得一提的是，memory引擎是支持非唯一哈希索引的。在数据库世界里是比较与众不同，如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中

B树

为磁盘存储而专门设计的一类平衡搜索树，细节可以阅读《树概述》

先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为

一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用B-Tree作为索引结构效率是非常高的

mysql实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

这里设表一共有三列，假设我们以Col1为主键，上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同

第一个重大区别是InnoDB的数据文件本身就是索引文件,MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录

主键索引是聚集索引还是非聚集索引？

在Innodb下主键索引是聚集索引，在Myisam下主键索引是非聚集索引

MyisAM索引 VS InnoDB索引

1. MyisAM支持全文索引（FULLTEXT）、压缩索引，InnoDB不支持；
2. InnoDB支持事务，MyisAM不支持；
3. MyisAM顺序储存数据，索引叶子节点保存对应数据行地址，辅助索引很主键索引相差无几；InnoDB主键节点同时保存数据行，其他辅助索引保存的是主键索引的值；
4. MyisAM键值分离，索引载入内存（key_buffer_size），数据缓存依赖操作系统；InnoDB键值一起保存，索引与数据一起载入InnoDB缓冲池；MyisAM主键（唯一）索引按升序来存储存储，InnoDB则不一定
5. MyisAM索引的基数值（Cardinality，show index 命令可以看见）是精确的，InnoDB则是估计值。这里涉及到信息统计的知识，MyisAM统计信息是保存磁盘中，在alter表或Analyze table操作更新此信息，而InnoDB则是在表第一次打开的时候估计值保存在缓存区内；
6. MyisAM处理字符串索引时用增量保存的方式，如第一个索引是‘preform’，第二个是‘preformence’，则第二个保存是‘7，ance’，这个明显的好处是缩短索引，但是缺陷就是不支持倒序提取索引，必须顺序遍历获取索引

查询

查询过程

在收到一个查询的时候，Mysql的架构中的各个组件是如此工作的：

客户端同数据库服务层建立TCP连接，连接管理模块会建立连接，并请求一个连接线程。如果连接池中有空闲的连接线程，则分配给这个连接，如果没有，在没有超过最大连接数的情况下，创建新的连接线程负责这个客户端。

在真正的操作之前，还需要调用用户模块进行授权检查，来验证用户是否有权限。通过后，方才提供服务，连接线程开始接收并处理来自客户端的SQL语句。

连接线程接收到SQL语句之后，将语句交给SQL语句解析模块进行语法分析和语义分析。

如果是一个查询语句，则可以先看查询缓存中是否有结果，如果有结果可以直接返回给客户端。

如果查询缓存中没有结果，就需要真的查询数据库引擎层了，于是发给SQL优化器，进行查询的优化。如果是表变更，则分别交给insert, update, delete, create，alter处理模块进行处理。

接下来就是请求数据库引擎层，打开表，如果需要的话获取相应的锁。

接下来的处理过程就到了数据库引擎层，例如InnoDB。

在数据库引擎层，要先查询缓存页中有没有相应的数据，如果有则可以直接返回，如果没有就要从磁盘上去读取。

当在磁盘中找到相应的数据之后，则会加载到缓存中来，从而使得后面的查询更加高效，由于内存有限，多采用变通的LRU表来管理缓存页，保证缓存的都是经常访问的数据。

获取数据后返回给客户端，关闭连接，释放连接线程，过程结束。

结构

先来一张带主键的表，如下所示，pId是主键

如上图所示，分为上下两个部分，上半部分是由主键形成的B+树，下半部分就是磁盘上真实的数据！那么，当我们， 执行下面的语句

1

select * from table where pId='11'

查询过程：

如上图所示，从根开始，经过3次查找，就可以找到真实数据。如果不使用索引，那就要在磁盘上，进行逐行扫描，直到找到数据位置。显然，使用索引速度会快。但是在写入数据的时候，需要维护这颗B+树的结构，因此写入性能会下降！

再创建一个非聚簇索引：

1

create index index_name on table(name);

结构图如下所示

会根据你的索引字段生成一颗新的B+树。因此， 我们每加一个索引，就会增加表的体积， 占用磁盘存储空间。然而，注意看叶子节点，非聚簇索引的叶子节点并不是真实数据，它的叶子节点依然是索引节点，存放的是该索引字段的值以及对应的主键索引(聚簇索引)

1

select * from table where name='lisi'

查询过程：

通过上图红线可以看出，先从非聚簇索引树开始查找，然后找到聚簇索引后。根据聚簇索引，在聚簇索引的B+树上，找到完整的数据！

什么情况不去聚簇索引树上查询呢？

还记得我们的非聚簇索引树上存着该索引字段的值么。如果，此时我们执行下面的语句

1

select name from table where name='lisi'

查询过程

如上图红线所示，如果在非聚簇索引树上找到了想要的值，就不会去聚簇索引树上查询

再创建一个非聚簇索引：

1

create index index_birthday on table(birthday);

多加一个索引，就会多生成一颗非聚簇索引树。因此，很多文章才说，索引不能乱加。因为，有几个索引，就有几颗非聚簇索引树！你在做插入操作的时候，需要同时维护这几颗树的变化！因此，如果索引太多，插入性能就会下降

最左原则

最左原则，并不是指 SQL 语句的 where 顺序要和联合索引一致

当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的，

比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向

如果name相同再依次比较age和sex，最后得到检索的数据；

但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询

比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了

参考资料

mysql索引最左匹配原则的理解?

MySQL索引背后的数据结构及算法原理

B树、B-树、B+树、B*树【转】,mysql索引

索引原理与慢查询优化

MySQL(Innodb)索引的原理

前言

之前的排序算法 《快速排序》 与 《归并排序》 都使用了递归手法，如果不能理解递归，那分治思想类算法实现就难以理解

递归

To iterate is human,to recurse divine. — L. Peter Deutsch

迭代的是人，递归的是神

递归思想

递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

递归中的“递”就是入栈，递进；“归”就是出栈，回归

规模大转化为规模小是核心思想，但递归并非是只做这步转化，而是把规模大的问题分解为规模小的子问题和可以在子问题解决的基础上剩余的可以自行解决的部分。而后者就是归的精髓所在，是在实际解决问题的过程

为什么我老是有递归没有真的在解决问题的感觉？

因为递是描述问题，归是解决问题。而我的大脑容易被递占据，只往远方去了，连尽头都没走到，何谈回的来

递归就是有去（递去）有回（归来）

• 为什么可以”有去“？

这要求递归的问题需要是可以用同样的解题思路来回答除了规模大小不同其他完全一样的问题

• 为什么可以”有回“？

这要求这些问题不断从大到小，从近及远的过程中，会有一个终点，一个临界点，一个baseline，一个你到了那个点就不用再往更小，更远的地方走下去的点，然后从那个点开始，原路返回到原点

递归三要素

用程序表达出来，确定了三个要素：递 + 结束条件 + 归

1
2
3
4
5
6
7
8

function recursion(大规模){
    if (end_condition)    {
        end;     
    } else {     //先将问题全部描述展开，再由尽头“返回”依次解决每步中剩余部分的问题
        recursion(小规模);     //go;
        solve;                //back;
    }
}

另一种递归情况，比如递归遍历的二叉树的先序

1
2
3
4
5
6
7
8

function recursion(大规模){
    if (end_condition){
        end;     
    }else{     //在将问题转换为子问题描述的每一步，都解决该步中剩余部分的问题。
        solve;                //back;
        recursion(小规模);     //go;
    }
}

示例

阶乘

求一个数的阶乘是练习简单而典型的例子，阶乘的递推公式为：factorial(n)=n*factorial(n-1)，其中n为非负整数,且0!=1,1!=1

我们根据递推公式可以轻松的写出其递归函数：

1
2
3
4
5
6
7
8

public static long factorial(int n) throws Exception {
    if (n < 0)
        throw new Exception("参数不能为负！");
    else if (n == 1 || n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

在求解6的阶乘时，递归过程:

斐波那契数列

斐波那契数列的递推公式:Fib(n)=Fib(n-1)+Fib(n-2)，指的是如下所示的数列：

1、1、2、3、5、8、13、21…..

按照其递推公式写出的递归函数如下：

1
2
3
4
5
6
7
8

public static int fib(int n) throws Exception {
    if (n < 0)
        throw new Exception("参数不能为负！");
    else if (n == 0 || n == 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

VS迭代

递归算法与迭代算法的设计思路区别在于：函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法

参考资料

怎么更好地终极理解递归算法

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

定义

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法

归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括”从上往下“和”从下往上“2种方式

从上往下的归并排序：

1. 分解 – 将当前区间一分为二，即求分裂点 mid = (low + high)/2
2. 求解 – 递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1
3. 合并 – 将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]

从下往上的归并排序：

1. 将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；
2. 得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；
3. 直接合并成一个数列为止。这样就得到了我们想要的排序结果。

归并步骤

• 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
• 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
• 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾

比如合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤

演示

实现

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

/**
 * 归并排序
 * @param array
 * @param left
 * @param right
 */
private static void mergeSort(int []array,int left,int right){
    if(left < right) {
        //分解
        int mid = (left + right) / 2;
        mergeSort(array,left,mid);
        mergeSort(array,mid + 1,right);
        //合并
        merge(array,left,mid,right);
    }
}

static void merge(int []array,int left,int mid,int right) {
    System.out.println("merge->left:"+left+" mid:"+mid+" rgiht:"+right);
    int i = left;
    int j = mid +1;
    int tmp[] = new int[right-left+1];//构建tmp数组
    int t = 0;//tmp数组索引
    //填充tmp数组
    for (;i<=mid && j<=right;) {
        if(array[i] < array[j]) {
            tmp[t++] = array[i++];
        } else {
            tmp[t++] = array[j++];
        }
    }
    while (i<=mid) {
        tmp[t++] = array[i++];
    }
    while (j<=right) {
        tmp[t++] = array[j++];
    }

    //再把tmp复制到array
    t = 0;
    while (left<=right) {
        array[left++] = tmp[t++];
    }
    System.out.println("  tmp:"+ Arrays.toString(tmp));
    System.out.println("merge:"+ Arrays.toString(array));
}

复杂度

归并排序的时间复杂度是O(N*lgN)

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？

归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(N*lgN)

VS 快速排序

归并排序（MergeSort）和快速排序(QuickSort)都是用了分治算法思想。

所谓分治算法，顾名思义，就是分而治之，就是将原问题分割成同等结构的子问题，之后将子问题逐一解决后，原问题也就得到了解决。

同时，归并排序（MergeSort）和快速排序(QuickSort)也代表了两类分治算法的思想。

对于归并排序，我们对于待处理序列怎么分的问题上并没有太多关注，仅仅是简单地一刀切，将整个序列分成近乎均匀的两份，然后将子序列进行同样处理。但是，我们更多的关注点在于怎么把分开的部分合起来，也就是merge的过程。

对于快速排序来说，我们则是花了很大的功夫放在了怎么分这个问题上，我们设定了枢轴（标定点），然后通过partition的过程将这个枢轴放在合适的位置，这样我们就不用特别关心合起来的过程，只需要一步一步地递归下去即可。

归并排序是由下向上的，先处理子数组然后再合并。而快速排序正好相反，它的过程是由上向下的，先分出两个子区间，再对子区间进行排序。归并排序是稳定的时间复杂度为 O(n)O(n)，但它是非原地算法，在进行子数组合并的时候，我们需要临时申请一个数组来暂时存放排好序的数据。因为这个临时空间是可以重复利用的，因此归并排序的空间复杂度为 O(n)，最多需要存放 n 个数据；
而快排则是原地排序算法

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

定义

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆

堆是一棵顺序存储的完全二叉树

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。

其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

举例来说，对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时，称之为堆：

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整;

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

完全二叉树

完全二叉树的定义是建立在满二叉树定义的基础上的，而满二叉树又是建立在二叉树的基础上的。

二叉树

二叉树是树的特殊一种，具有如下特点：

1. 每个结点最多有两颗子树，结点的度最大为2。
2. 左子树和右子树是有顺序的，次序不能颠倒。
3. 即使某结点只有一个子树，也要区分左右子树。

满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。就是完美圆满的意思，关键在于树的平衡

根据满二叉树的定义，得到其特点为：

1. 叶子只能出现在最下一层。
2. 非叶子结点度一定是2.
3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

完全二叉树

对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树

在上图中，树1，按层次编号5结点没有左子树，有右子树，10结点缺失。树2由于3结点没有字数，是的6,7位置空挡了。树3中结点5没有子树。

上图就是一个完全二叉树

算法

利用堆顶记录的是最大(以大顶堆为例)关键字这一特性，每一轮取堆顶元素放入有序区，就类似选择排序每一轮选择一个最大值放入有序区，可以把堆排序看成是选择排序的改进。

1. 将初始待排序关键字序列(R0,R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

2. 将堆顶元素R[0]与最后一个元素R[n]交换，此时得到新的无序区(R0,R1,R2,……Rn-1)和新的有序区(Rn)；

3. 由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,R2,……Rn-1)调整为新堆

不断重复此2、3步骤直到有序区的元素个数为n-1，则整个排序过程完成

演示

1. 由一个无序序列建成一个堆
2. 输出堆顶元素之后，调整剩余元素成为一个新的堆

1.构造堆

构造初始堆,将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)

数组是一个无序结构

因为(n/2-1)~0的节点才有子节点，n=5,(n/2-1) = 1 即1 0节点才有子节点

所以将1 0节点从下到上，从右到左的与它自己的子节点比较并调整最终形成大顶堆

1. 节点1和它的子节点3 4的元素进行比较，最大者作为父节点

2. 将节点0和它的子节点1 2的元素进行比较，最大者为父节点

3. 交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6

构造完成将一个无需序列构造成了一个大顶堆

2. 调整堆

将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

1. 将堆顶元素9和末尾元素4进行交换

2. 重新调整结构，使其继续满足堆定义

3. 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8

4. 继续进行调整，交换，如此反复进行，最终使得整个序列有序

实现

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

 /**
 *
 * a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

 　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

 　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

 * 整个排序过程，就是构造堆的过程
 *
 * 这儿写得利于理解一点，把最后一步改掉，循环从数组中把第一位取出来放到新数组，剩余的再去构造堆
 * @param array
 */
static void heapSort(int []array) {
    //原始数组
    int [] oriental = Arrays.copyOf(array,array.length);
    //最终排序好的数组
    int [] result = new int[array.length];

    int length = array.length;
    for ( int i = 0;i< length;i++) {
        //1.构造堆
        buildHeap(array);
        //构建完array[0]就是最大的元素,取出来放到排序好的数组
        result[i] = array[0];
        //[0]取走之后，一个新数组，再去构造堆
        array = Arrays.copyOfRange(array, 1,length-i);
    }
    System.out.println("finish:"+ Arrays.toString(result));
}

/**
 * 构造椎
 * @param array
 */
static void buildHeap(int []array) {
    //(n/2-1)~0的节点才有子节点
    for (int i= array.length/2 -1 ;i>=0;i--) {
//            System.out.println("i:"+i);
//            System.out.println("start:"+ Arrays.toString(array));
        int k = i;
        for (int left = k * 2 + 1; left < array.length; left = k * 2 + 1) {
           // System.out.println("build:"+ Arrays.toString(array));
            int max = left;
            int right = left + 1;
            //有右节点
            if (right < array.length) {
                if (array[right] > array[left]) {
                    max = right;
                }
            }
            //max是left子节点,那就交换左子节点与k
            if (array[max] > array[k]) {
                swap(array, max, k);
                // 下面就是非常关键的一步了
                // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
                // 所以，循环对子节点所在的树继续进行判断
                k = left;
            } else {
                break;
            }
        }
    }
    //System.out.println("  end:"+ Arrays.toString(array));
}

详细代码：
https://github.com/zhuxingsheng/javastudy/tree/master/src/main/java/com/jack/algorithms/sort

复杂度

参考资料

图解排序算法(三)之堆排序

图解堆排序

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

定义

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

算法

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

1. 初始状态：无序区为R[1..n]，有序区为空
2. 第1趟排序
   在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
   ……
3. 第i趟排序
   第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

演示

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

static void selectSort(int []array) {
    for (int i=0;i<array.length-1;i++) {
        int min  = i;
        for (int j = i+1;j<array.length;j++){
            if(array[min] > array[j]) {
                min = j;
            }
        }
        if( min != i) {
            int tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;
        }

    }
}

复杂度

比较次数：T = （n-1)）+ （n -2）+（n - 3）…. + 1; T = [n*(n-1) ] / 2；

交换次数：

最好的情况全部元素已经有序，则交换次数为0；

最差的情况，全部元素逆序，就要交换 n-1 次；

空间复杂度

最优的情况下（已经有顺序）复杂度为：O(0)

最差的情况下（全部元素都要重新排序）复杂度为：O(n );

平均的时间复杂度：O(1)

VS 插入排序

插入排序特别的相似

复杂度一样，但是插入排序和读入（初始）的数据有关，最优情况只有O(n)；而选择排序不论如何，永远都是O(n^2)

插入排序是边读边排，每当读入一个新的数时，目前的数组一定是排好序的。而选择排序不同，它必须是读完所有的数据之后才能开始排序的。

那么选择排序的缺点就是，万一数据量很大，比方说一百万个，光读就慢了，还要排序，那就更慢了。如果这两个耗时的步骤可以并行一起做的话，显然插入排序肯定就会快一些。

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

定义

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一

算法

直接插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次

是否能够减少这样的移位呢？不希望是一步一步的移动，而是大步大步的移动。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

初始时,有一个大小为 10 的无序序列

在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组

接下来,按照直接插入排序的方法对每个组进行排序

在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组

按照直接插入排序的方法对每个组进行排序

在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组

按照直接插入排序的方法对每个组进行排序。此时,排序已经结束

演示

• 1.增量N/2=4分组

{35, 14}, {33, 19}, {42, 27} , {10, 44}

排序完：

• 2.增量N/2/2=2分组

{14, 27, 35, 42}, {19, 10, 33, 44}

排序完：

• 3.增量N/2/2/2=1分组排序

也可以通过动画更清晰了解整个排序过程

动画：http://www.zhuxingsheng.com/tools/sort/sort.html

分组排序后，他们的索引还是保留在原始索引中，来两个更加直观的动画演示

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

static void shellSort(int []array) {
        //以length/2为增量
        for (int gap=array.length/2;gap>0;gap= gap/2) {
            //以gap分组，进行排序
           for(int i = gap;i<array.length;i++){
               int tmp = array[i];
               int j = i - gap;
               //相对直接插入，步长从1变成了gap
               while ( j>=0 && tmp<array[j] ) {
                   array[j+gap] = array[j];
                   j=j-gap;
               }
               array[j+gap] = tmp;
           }
        }
    }

复杂度

希尔排序的时间复杂度与增量(即，步长gap)的选取有关

{1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n²)

Hibbard提出了另一个增量序列{1,3,7，…,2^k-1}，这种序列的时间复杂度(最坏情形)为O(n^1.5)

Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,…}

1

9×4^i−9×2i+1  和 4^i−3×2^i+1  这两个算式

其中， i=0,1,2,⋯ 时，第一个式子计算出的值分别为1，19，109，……； i=2,3,⋯ 时，第二个式子算出的值分别为5，41，……

前言

其实不只在微服务中，在平常网络请求，或者与第三方系统进行交互都需要设置超时时间

为什么需要超时与重试？ 总体上讲，肯定是为了增加系统可靠性，具体表现在两个方面

1. 系统自我保护：
   快速失败，在业务最大允许等待时间内未收到返回数据，主动放弃等待，释放占用资源，避免请求不断累积带来的客户端雪崩效应
2. 成功率：服务处理超时原因有很多，但常见的超时都是短暂的，主要是GC，或者有网络抖动等。这些短时间影响服务端状态的情况而造成请求成功率下降，需要补救措施。简单的补救有超时重试操作：当前请求超时后，将会重试到非当前服务器，降低重试超时的机率

这一篇将由浅入深探索timeout机制，以及在微服务下的实践

超时

经常被提起的两种超时：connection timeout、socket timeout

通过最底层的Socket,ServerSocket演示一下这两种超时的表现，nio框架都会有对应的配置选项

connectionTimeout

建立连接超时时间

客户端,随便写个IP，设置一个timeout

1
2

Socket socket = new Socket();
socket.connect(new InetSocketAddress("10.0.0.1",8080),20000);

在timeout时间到时，就会抛出connect timed out异常

1
2
3
4
5
6
7
8
9

Exception in thread "main" java.net.SocketTimeoutException: connect timed out
	at java.net.DualStackPlainSocketImpl.waitForConnect(Native Method)
	at java.net.DualStackPlainSocketImpl.socketConnect(DualStackPlainSocketImpl.java:85)
	at java.net.AbstractPlainSocketImpl.doConnect(AbstractPlainSocketImpl.java:350)
	at java.net.AbstractPlainSocketImpl.connectToAddress(AbstractPlainSocketImpl.java:206)
	at java.net.AbstractPlainSocketImpl.connect(AbstractPlainSocketImpl.java:188)
	at java.net.PlainSocketImpl.connect(PlainSocketImpl.java:172)
	at java.net.SocksSocketImpl.connect(SocksSocketImpl.java:392)
	at java.net.Socket.connect(Socket.java:589)

socketTimeout

Enable/disable SO_TIMEOUT with the specified timeout, in milliseconds. With this option set to a non-zero timeout, a read() call on the InputStream associated with this Socket will block for only this amount of time. If the timeout expires, a java.net.SocketTimeoutException is raised, though the Socket is still valid. The option must be enabled prior to entering the blocking operation to have effect. The timeout must be > 0. A timeout of zero is interpreted as an infinite timeout.

服务端，只要让客户端能连接上就行，不发送数据

1
2
3
4
5

ServerSocket serverSocket = new ServerSocket(8080);
while ( true) {
    Socket socket = serverSocket.accept();
    new Thread(new P(socket)).start();
}

客户端，进行读数据

1
2
3

Socket socket = new Socket();
socket.connect(new InetSocketAddress("localhost",8080),20000);
socket.setSoTimeout(3000);

3s后，就抛出Read timed out

1
2
3
4
5
6

java.net.SocketTimeoutException: Read timed out
	at java.net.SocketInputStream.socketRead0(Native Method)
	at java.net.SocketInputStream.socketRead(SocketInputStream.java:116)
	at java.net.SocketInputStream.read(SocketInputStream.java:170)
	at java.net.SocketInputStream.read(SocketInputStream.java:141)
	at java.net.SocketInputStream.read(SocketInputStream.java:223)

nio

对NIO，看网上一些示例基本没有关注到这一点，所以值得思考，难道是nio不需要关注timeout?

客户端对服务器的连接:

1
2
3
4

Selector selector = Selector.open();
InetSocketAddress isa = new InetSocketAddress(host, port);
// 调用open静态方法创建连接到指定主机的SocketChannel
SocketChannel sc = SocketChannel.open(isa);

在调用SocketChannel.open()方法时,如果连接不上服务器,那么此方法就会长时间阻塞,为了解决这个问题,我们可以在调用open()方法前,启动一个定时器,这个定时器会在指定的时间内检查是否已连接成功,这个指定的时间也就是我们希望设置的连接超时时间,当检查已连接上服务器时,提示用户已连接成功;若没有连接上,可在代码中抛出SocketTimeoutException,并提示用户连接超时

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

public void connect(){
	try{
		selector = Selector.open();
		InetSocketAddress isa = new InetSocketAddress(host, port);
		//10秒连接超时
		new Timer().schedule(tt, 10000);
		// 调用open静态方法创建连接到指定主机的SocketChannel
		sc = SocketChannel.open(isa);
		// 设置该sc以非阻塞方式工作
		sc.configureBlocking(false);
		// 将Socketchannel对象注册到指定Selector
		sc.register(selector, SelectionKey.OP_READ);
		Message msg = new Message();
		msg.what = 0;
		msg.obj = sc;
		handler.sendMessage(msg); // 连接成功
		new Thread(new NIOReceiveThread(selector, handler)).start();
	}catch (IOException e)	{
		e.printStackTrace();
		handler.sendEmptyMessage(-1); // IO异常
	}
}
TimerTask tt = new TimerTask(){
	@Override
	public void run(){
		if (sc == null || !sc.isConnected()){
			try{
				throw new SocketTimeoutException("连接超时");
			}catch (SocketTimeoutException e){
				e.printStackTrace();
				handler.sendEmptyMessage(-6); // 连接超时
			}
		}
	}
};

在stackoverflow上有人回答了Read timeout for an NIO SocketChannel?

1. You are using a Selector, in which case you have a select timeout which you can play with, and if it goes off (select(timeout) returns zero) you close all the registered channels, or
2. You are using blocking mode, in which case you might think you should be able to call Socket.setSoTimeout() on the underlying socket (SocketChannel.socket()), and trap the SocketTimeoutException that is thrown when the timeout expires during read(), but you can’t, because it isn’t supported for sockets originating as channels, or
3. You are using non-blocking mode without a Selector, in which case you need to change to case (1).

netty

netty业界公认的高成熟nio产品，也是大多数微服务底层使用的通信框架，内部细节值得挖一挖处理方式，篇幅有限，另开篇深挖

先看在微服务产品中的使用

connectionTimeout

这种场景很简单，在使用netty时,对应的配置选项

1
2

Bootstrap b = new Bootstrap();
b.option(ChannelOption.CONNECT_TIMEOUT_MILLIS, 10000)

socketTimeout

这种场景各个框架在处理里，手法不尽相同，各有特色

motan

Motan是一套高性能、易于使用的分布式远程服务调用(RPC)框架，新浪微博开源。

之前解读过motan源码，《motan客户端解析》，《motan服务端解析》

NettyChannel.request：

1. 获取此method的配置timeout
2. 在write时，awaitUninterruptibly
3. 超时就抛出timeoutException

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

public Response request(Request request) throws TransportException {
    int timeout = nettyClient.getUrl().getMethodParameter(request.getMethodName(), request.getParamtersDesc(),
            URLParamType.requestTimeout.getName(), URLParamType.requestTimeout.getIntValue());
	if (timeout <= 0) {
           throw new MotanFrameworkException("NettyClient init Error: timeout(" + timeout + ") <= 0 is forbid.",
                   MotanErrorMsgConstant.FRAMEWORK_INIT_ERROR);
       }
	NettyResponseFuture response = new NettyResponseFuture(request, timeout, this.nettyClient);
	this.nettyClient.registerCallback(request.getRequestId(), response);

	ChannelFuture writeFuture = this.channel.write(request);

	boolean result = writeFuture.awaitUninterruptibly(timeout, TimeUnit.MILLISECONDS);

	if (result && writeFuture.isSuccess()) {
		response.addListener(new FutureListener() {
			@Override
			public void operationComplete(Future future) throws Exception {
				if (future.isSuccess() || (future.isDone() && ExceptionUtil.isBizException(future.getException()))) {
					// 成功的调用 
					nettyClient.resetErrorCount();
				} else {
					// 失败的调用 
					nettyClient.incrErrorCount();
				}
			}
		});
		return response;
	}

	writeFuture.cancel();
	response = this.nettyClient.removeCallback(request.getRequestId());

	if (response != null) {
		response.cancel();
	}

	// 失败的调用 
	nettyClient.incrErrorCount();

	if (writeFuture.getCause() != null) {
		throw new MotanServiceException("NettyChannel send request to server Error: url="
				+ nettyClient.getUrl().getUri() + " local=" + localAddress + " "
				+ MotanFrameworkUtil.toString(request), writeFuture.getCause());
	} else {
		throw new MotanServiceException("NettyChannel send request to server Timeout: url="
				+ nettyClient.getUrl().getUri() + " local=" + localAddress + " "
				+ MotanFrameworkUtil.toString(request));
	}
}

注意到其中的NettyResponseFuture，看名字就明白是个Future模式，在《代码小析 - 异步回调》中有分析过

接收到服务端返回

1
2
3
4
5
6
7
8
9
10
11
12
13

NettyResponseFuture responseFuture = NettyClient.this.removeCallback(response.getRequestId());
if (responseFuture == null) {
	LoggerUtil.warn(
			"NettyClient has response from server, but resonseFuture not exist,  requestId={}",
			response.getRequestId());
	return null;
}

if (response.getException() != null) {
	responseFuture.onFailure(response);
} else {
	responseFuture.onSuccess(response);
}

获取真实结果NettyResponseFuture.getValue()

通过long waitTime = timeout - (System.currentTimeMillis() - createTime);计算一下真正的wait时间

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

public Object getValue() {
	synchronized (lock) {
		if (!isDoing()) {
			return getValueOrThrowable();
		}

		if (timeout <= 0) {
			try {
				lock.wait();
			} catch (Exception e) {
				cancel(new MotanServiceException("NettyResponseFuture getValue InterruptedException : "
						+ MotanFrameworkUtil.toString(request) + " cost="
						+ (System.currentTimeMillis() - createTime), e));
			}

			// don't need to notifylisteners, because onSuccess or
			// onFailure or cancel method already call notifylisteners
			return getValueOrThrowable();
		} else {
			long waitTime = timeout - (System.currentTimeMillis() - createTime);

			if (waitTime > 0) {
				for (;;) {
					try {
						lock.wait(waitTime);
					} catch (InterruptedException e) {
					}

					if (!isDoing()) {
						break;
					} else {
						waitTime = timeout - (System.currentTimeMillis() - createTime);
						if (waitTime <= 0) {
							break;
						}
					}
				}
			}

			if (isDoing()) {
				timeoutSoCancel();
			}
		}
		return getValueOrThrowable();
	}
}

totalTimeout

有了timeout基本已经满足需求，但这儿再提一个totalTimeout，为什么需要一个总超时时间

比如客户端希望服务端在60ms内返回，由于成功率要求必须加一次重试，但是设置超时时间30ms重试一次会很浪费（绝大部分重试很快，但预留了30ms则压缩了初次调用的时间）。设置40ms重试一次就可能出现整体耗时大于60ms。所以希望可以配置整体超时时间为60ms，单次40ms加重试一次，这样既充分利用看重试机会也不会导致整体超过60ms

一次服务调用的正常请求的最长时间为：timeout * failovertimes + success_invocation_time

比如某个服务的timeout为100ms，failovertimes为1，正常调用的平均耗时为10ms，那么它的上游在重试情况下的耗时就是：乐观估计100 1+10=110ms；悲观估计100 1+100=200ms

为了保证总体超时时间，只能把单次超时时间压缩，使得某些情况下可能不需求重试的场景也进行了重试

对比一下，设置totalTimeout与不设置的情况：

1. 某服务通常能在20ms返回，但是因为某些意外（比如gc），连续两次都要40ms

• 只能设置单次timeout的情况下，timeout=30ms，failovertimes=1
  因此对于client来说，它看到的调用耗时就是：30ms（超时） + 30ms（超时） = 60ms
• 分开设置首次超时和总体超时的情况下，timeout=40ms，total_timeout=60ms，failovertimes=1
  因此对于client来说，它看到的调用耗时就是：40ms（超时）+ （60ms-40ms）（超时） = 60ms

2. 某服务通常能在20ms返回，但是因为某些意外（比如gc），这次需要35ms才能返回。

• 只能设置单次timeout的情况下，timeout=30ms，failovertimes=1。
  因此对于client来说，它看到的调用耗时就是：30ms（超时） + 20ms = 50ms
• 分开设置首次超时和总体超时的情况下，timeout=40ms，total_timeout=60ms，failovertimes=1。
  因此对于client来说，它看到的调用耗时就是：35ms（正常返回） = 35ms

重试

因某个服务实例短暂状态不佳而造成的超时，使用重试处理可以让请求转向其他服务实例的做法可以很好改善非集中式问题的成功率。

但如果超时重试只做简单的重试策略：有超时便重试，这样可能会导致服务端的崩溃。

例如：当前基础组件（如db）压力过大而造成超时，如果一律重试的话，会导致服务端集群实际接受请求量翻倍，这会使得基础组件压力无减反增，可能会导致其最终崩溃

实现

• 思路简单，配置重试次数，出现非业务异常就重试，达到次数上限或者中途成功结束
• 重试限流,重试造成雪崩的可能性，所以重试需要控制流量

motan

之前解读过motan源码，《motan客户端解析》，motan的failover就是这么处理的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 先使用method的配置
int tryCount =
        refUrl.getMethodParameter(request.getMethodName(), request.getParamtersDesc(), URLParamType.retries.getName(),
                URLParamType.retries.getIntValue());
// 如果有问题，则设置为不重试
if (tryCount < 0) {
    tryCount = 0;
}

for (int i = 0; i <= tryCount; i++) {
    Referer<T> refer = referers.get(i % referers.size());
    try {
        request.setRetries(i);
        return refer.call(request);
    } catch (RuntimeException e) {
        // 对于业务异常，直接抛出
        if (ExceptionUtil.isBizException(e)) {
            throw e;
        } else if (i >= tryCount) {
            throw e;
        }
        LoggerUtil.warn(String.format("FailoverHaStrategy Call false for request:%s error=%s", request, e.getMessage()));
    }
}

超时重试

但像我司框架就没有这样处理，只关注超时重试，因为超时重试主要是解决因偶尔短暂状态不佳而对成功率造成的影响，所以把重点放在处理短暂处于超时状态超时请求，对于长时间处于较大量的超时状态时，将选择不进行重试fail fast

限流

主要是防止重试次数过多，引起系统雪崩，有必要进行一下限流

在《微服务-熔断机制》中提到过限流算法，细节可参考《计数器算法》

参考资料

Read timeout for an NIO SocketChannel?