分区表

MySQL分区表的底层由多个物理子表组成，每个分区表都有一个使用#分隔命名的表文件。分区表对SQL层是透明的，，对分区表的请求会通过分区表的句柄（Handler Object）转化成对存储引擎接口的调用。每个分区表有自己的独立索引，整个表没有全局索引。查询时，优化器根据分区定义过滤不包含查询数据的分区。分区表是一种粗粒度的索引策略，单表最多1024个分区（最好不超过150），分区表无法使用外键约束。

分区表适用于以下场景：

1. 在没有合适索引时，对其中几个分区进行全表扫描
2. 表太大，无法放入内存
3. 部分分区是热点域（例如按时间分区时，只有最近的记录是热点域）
4. 需要对分区表进行独立操作（清除、检查、优化、备份、恢复或者使用不同的物理设备）
5. 使用分区表规避特殊限制（如InnoDB的单个索引互斥访问，ext3文件系统的inode锁竞争等）

分区表使用方法

1
2
3
4
5
6
7

create table sales {
    order_date DATATIME NOT NULL,
    ...
}ENGINE=InnoDN PARTITION BY RANGE(YEAR(order_date)) {
    PARTITION p2012 VALUES LESS THEN(2012),
    PARTITION p2013 VALUES LESS THEN(2013),
}

视图

视图是一种虚拟的数据表，它的行为和数据表一样，但是并不真正包含数据，但是不能对视图创建索引和触发器。实现视图的两种方法：

1. 将SELECT语句的结果放到临时表中，即临时表算法（TEMPTABE），使用这种算法会有明显的性能问题。
2. 重写使用视图的查询语句，将视图定义SQL合并到查询SQL中，即合并算法（MERGE）。

如果视图中包含GROUP BY，DISTINCT，聚合函数，UNION，子查询等，原表记录和视图记录中无法建立一一映射，MySQL将使用临时表算法来实现视图。可以通过视图来更新视图相关数据表的视图成为可更新视图，更新视图查询也可以是关联语句，但是被更新的列必须来自同一个表，所有使用临时表算法的视图都无法被更新。

Mysql服务器逻辑架构

最上层：连接/线程处理，提供连接处理、授权认证、安全等服务（与其他客户端/服务器C/S架构类似）

第二层：包含了MySql大多数的核心服务功能，包括查询解析、分析、优化、缓存以及所有内置函数（日期、时间、数学、加密……），所有跨存储引擎的功能都在这一层实现：存储过程、触发器、视图等。

最下层：存储引擎，存储引擎负责Mysql中数据的存储和提取，上层通过存储引擎API与存储引擎通信，这些API屏蔽了不同存储引擎之间的差异，执行诸如“开始一个事务”或者“根据主键提取一行记录”等操作。除了InnoDB外，存储引擎不会解析SQL（InnoDB会解析外键定义，因为MySql服务器本身没有实现这一功能），不同存储引擎之间不会相互通信。

连接管理与安全性

每个客户端连接都会在服务器进程中拥有一个线程，这个连接查询只会在这个单独的线程中执行，该线程只能轮流在某个CPU核中执行。

并发读写

在处理并发读写时，可以通过共享锁（Shared Lock，也叫读锁read lock）和排它锁（Exclusive Lock，也叫写锁write lock）来控制。

读锁是共享的，读锁之间互不阻塞，多个客户端可以在同一个时刻读取同一个资源而互不干扰；写锁是排它的，写锁会阻塞其它写锁或读锁。这样可以保证在某个时刻只有一个用户能执行写入。锁策略就是在锁的开销和数据安全性之间寻求平衡，大多数商业数据库都是在表上施加行级锁（row-level lock），并以多种方式实现，以便在锁比较多的情况下提供尽可能好的性能。MySql则提供了更多的选择，MySql存储引擎可以实现自己的锁策略和锁粒度。

表锁（table lock）是MySql中最基本的锁，也是开销最小的锁，它会锁定整个表。写操作（插入、删除、更新）时必须先获取写锁，这会阻塞其它用户对该表的所有读写操作。写锁比读锁有更高的优先级，写锁请求可能会被插入到读锁队列前面。除了存储引擎可以管理自己的锁外，MySql本身也会使用表锁来实现不同的目的，例如Alter Table时MySql会使用表锁。行锁(row lock)可以最大程度地支持并发处理，同时也带来了最大的锁开销（InnoDB和XtraDb）中实现了行锁，行锁只在存储引擎中实现，MySql服务器中没有实现。

网络爬虫在爬完网页后需要计算网页之间的相似度以进行排序等步骤，如何快速计算文本之间的相似度呢？

1. 最Brute-force的方法是逐字比较字符是否相同，然后统计结果
2. 更好一点的办法可以计算文本间的编辑距离，这是一个很好的办法，但是在文本很长，数据量很大时，时间和空间复杂度还是非常可观的
3. 对文本进行分词，抽取特征向量（一般使用TF-IDF，Iterm Frequency-Inverse Document Frequency），然后通过两个特征向量之间的余弦夹角来衡量两个文本的相似度，这种算法几何意义明确，计算复杂度也不是很高，是一种非常好的算法
4. 如果需要处理海量数据，就需要采用一些降维技术，本文中的Simhash算法就适合于计算海量文本相似度的场景

Simhash介绍

Simhash是一种局部敏感的哈希算法（locality sensitive hash，LSH），采用了降维技术，将高维的特征向量降低到固定个bit位中。使用Simhash算法计算文本相似度的流程如下：

1. 将一个 f 维的向量 V 初始化为0；f 位的二进制数 S 初始化为0；
2. 对每一个特征：用传统的 hash 算法对该特征产生一个 f 位的签名 b。
3. 对 i=1 到 f：如果 b 的第 i 位为1，则 V 的第 i 个元素加上该特征的权重；否则，V 的第 i 个元素减去该特征的权重。
4. 如果 V 的第 i 个元素大于0，则 S 的第 i 位为1，否则为0；
5. 输出 S 作为签名。

这个算法相当于随机产生了f个n维超平面，每个超平面将向量v所在的空间一分为二，v在这个超平面上方则得到一个1，否则得到一个0，然后将得到的f个0或1组合起来成为一个f维的签名。如果两个向量u, v的夹角为θ，则一个随机超平面将它们分开的概率为θ/π，因此u, v的签名的对应位不同的概率等于θ/π。所以，我们可以用两个向量的签名的不同的对应位的数量，即汉明距离，来衡量这两个向量的差异程度。

参考资料

利用Simhash快速查找相似文档

Simhash原理

Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/

DP

记录当前Bar左边和右边的最大高度，取两个最大高度的最小值min，当前Bar对总结果的贡献为min-当前Bar的高度，将每个Bar对结果的贡献累加起来即可。该算法时间复杂度2N，空间复杂度O(N)。

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

public int trap(int[] height) {
    if(height == null || height.length == 0) return 0;
    int sum = 0, rightMax = 0;
    int[] right = new int[height.length];
    for(int i = height.length - 1; i >= 0; --i) {
        right[i] = rightMax;
        rightMax = Math.max(rightMax, height[i]);
    }
    int leftMax = 0;
    for(int i = 0; i < height.length; ++i) {
        int water = Math.min(right[i], leftMax) - height[i];
        if(water > 0)
            sum += water;
        leftMax = Math.max(leftMax, height[i]);
    }
    return sum;
}

Two Pointers

使用两个指针l和r，初始时l指向第一个Bar，r指向最后一个Bar。然后每次从l和r指向的Bar选出高度最小的。如果l-Bar较小，那么统计l-Bar右面比l-Bar高度小的Bar与l-Bar的差值，直到右面的高度值超过l-Bar。r-Bar类似向左统计。两个指针相遇结果就统计完成。该算法时间复杂度N，空间复杂度O（1）。另一个巧妙使用多指针思想的题目：http://jeffzzf.github.io/2015/07/01/Sort-colors/

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

public int trap(int[] height) {
    if(height == null || height.length == 0) return 0;
    int l = 0, r = height.length - 1, sum = 0;
    while(l < r) {
        int min = Math.min(height[l], height[r]);
        if(min == height[l]) {
            while(l < r && min > height[++l])
                sum += min - height[l];
        } else {
            while(l < r && min > height[--r])
                sum += min - height[r];
        }
    }
    return sum;
}

类似于Trapping rain water，不过不是找出最大的容器而是计算所有边容纳的水量。采用类似的思路，维护首尾两个指针以及从两端开始的最大高度，每次从容器高度小得一端收缩，计算与维护的最大高度相比的差值，累加后的值即为总的水量。

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

public int trap(int[] height) {
    if(height == null || height.length <= 1) return 0;
    int n = height.length;
    int maxLeft = 0, maxRight = 0;
    int left = 0, right = n - 1;
    int result = 0;
    while(left < right) {
        if(height[left] < height[right]) {
            maxLeft = Math.max(maxLeft, height[left]);
            result += maxLeft - height[left];
            ++left;
        } else {
            maxRight = Math.max(maxRight, height[right]);
            result += maxRight - height[right];
            --right;
        }
    }
    return result;
}

在Mac下读取Windows下生成的txt文件时总是出现乱码，试了好多种办法都不奏效，几欲崩溃。在编码问题上已经栽了好多次跟头了，之前搞PHP+MySql时也被编码问题整得焦头烂额。

好在最终还是找到了解决办法，思路如下。

Windows平台编码

Windows平台的默认编码是ANSI，所谓ANSIAmerican National Standards Institute，ANSI）就是就是用2个字节来表示一个字符的方法，ANSI编码使用0X80-0xFF（ASCII使用00000000-11111110）七位来表示128个字符。

不同的国家和地区制定了不同的标准，由此产生了 GB2312、GBK、GB18030、Big5、Shift_JIS 等各自的编码标准。这些使用多个字节来代表一个字符的各种汉字延伸编码方式，称为 ANSI 编码。在简体中文Windows操作系统中，ANSI 编码代表 GBK 编码；在繁体中文Windows操作系统中，ANSI编码代表Big5；在日文Windows操作系统中，ANSI 编码代表 Shift_JIS 编码。

MAC平台编码

MAC平台使用的是Unique编码方案，而JVM的默认编码依赖于平台，所以一开始使用BufferedReader reader = new BufferedReader(new FileReader("file.txt"))时，使用的是Mac平台默认的解码器。这点可以在JDK文档中找到：

Every instance of the Java virtual machine has a default charset, which may or may not be one of the standard charsets. The default charset is determined during virtual-machine startup and typically depends upon the locale and charset being used by the underlying operating system.

同时，通过追踪BufferedReader，终于在StreamDecoder类中发现
if(var2 == null) { var3 = Charset.defaultCharset().name(); }
而System.out.print(Charset.defaultCharset().name());妥妥地输出UTF-8

解决方案

Dungeon Game

题目大意：公主被困在迷宫的右下角，骑士初始位于迷宫的左上角。迷宫的每个单元格（包括左上角和右下角）都有一个整数值x，如果x < 0，骑士到达该单元格时掉|x|的血；如果x > 0骑士在该单元格加|x|的血；如果 x == 0，骑士的血不掉也不加。如果骑士的血为0，那么他马上死亡。

要使骑士活着见到公主，那么骑士出发时最少需要加多少血。
https://leetcode.com/submissions/detail/32832133/

如果按照常规思维，从左上角到右下角的计算顺序，需要保存到某个单元格时最少需要的血以及剩下的血。如果逆向思维一下，从右下角向左上角计算，如果单元格需要更多的血，就加上需要的血；否则减去当前需要的血值。这种思维方式可以简化解题思路。

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

public int calculateMinimumHP(int[][] d) {
    if(d == null || d.length == 0 || d[0].length == 0) return 1;
    int[][] dp = new int[d.length][d[0].length];
    for(int i = d.length - 1; i >= 0; --i) {
        for(int j = d[0].length - 1; j >= 0; --j) {
            if(i == d.length - 1 && j == d[0].length -1)
                dp[i][j] = Math.max(1, 1 - d[i][j]);
            else if(i == d.length - 1)
                dp[i][j] = Math.max(1, dp[i][j + 1] - d[i][j]);
            else if(j == d[0].length - 1)
                dp[i][j] = Math.max(1, dp[i + 1][j] - d[i][j]);
            else
                dp[i][j] = Math.max(1, Math.min(dp[i][j + 1], dp[i + 1][j]) - d[i][j]);
        }
    }
    return dp[0][0];
}

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

https://leetcode.com/problems/triangle/

1
2
3
4
5
6
7
8
9
10
11

public int minimumTotal(List<List<Integer>> tri) {
    if(tri == null || tri.size() == 0) return 0;
    int len = tri.get(tri.size() - 1).size();
    int[] dp = new int[len + 1];
    for(int i = len - 1; i >= 0; --i) {
        List<Integer> list = tri.get(i);
        for(int j = 0; j < list.size(); ++j)
            dp[j] = list.get(j) + Math.min(dp[j], dp[j + 1]);
    }
    return dp[0];
}

Wildcard Matching
Implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “*”) → true
isMatch(“aa”, “a*”) → true
isMatch(“ab”, “?*”) → true
isMatch(“aab”, “cab”) → false

https://leetcode.com/problems/wildcard-matching/

基于DP的解法一（二维数组）

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

public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    if (p.replace("*", "").length() > s.length())
        return false;
    if(s.length() == 0) return true;
    boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
    dp[0][0] = true;
    for(int i = 0; i < p.length(); ++i) {
        if(p.charAt(i) == '*') dp[i + 1][0] = dp[i][0];
        for(int j = 0; j < s.length(); ++j) {
            if(p.charAt(i) == '*')
                dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j] ;
            else
                dp[i + 1][j + 1] = dp[i][j] && (p.charAt(i) == '?' || s.charAt(j) == p.charAt(i));
        }
    }
    return dp[p.length()][s.length()];
}

基于DP的解法二（一维数组）

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

public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    if (p.replace("*", "").length() > s.length())
        return false;
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for(int i = 0; i < p.length(); ++i) {
        if(p.charAt(i) == '*') {
            for(int j = 0; j < s.length(); ++j)
                dp[j + 1] = dp[j] || dp[j + 1];
        } else {
            for(int j = s.length() - 1; j >= 0; --j)
                dp[j + 1] = (s.charAt(j) == p.charAt(i) || p.charAt(i) == '?') && dp[j];
            dp[0] = dp[0] && p.charAt(i) == '*';
        }
    }
    return dp[s.length()];
}

哈希函数

哈希函数（散列函数，Hash Function）是一种从任何数据中创建数字指纹的方法，如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。

常用构造方法

1. 直接定址法：hash(key) = a*key + b
2. 折叠法： 取数据的某部分进行折叠计算： 12536798 ——> 1253 + 6798
3. 平方取中 ： 类似随机数产生的算法，取中间一部分作为地址
4. 除数取余法：hash(key) = key mod p（p一般取质素或者不包含小于20质因数的合数）
5. 随机数法：hash(key) = rand(key) key作为随机数的种子。（1-4方法都可以归入这类。因为平方取中和取余是常见随机数算法）
6. 根据数据特征分析
7. 综合法

BloomFilter

BloomFilter（布隆过滤器）是一种多哈希映射的快速查找算法，一般用来快速判断一个对象是否属于某个集合，例如最常用的网络爬虫中的地址去重策略。

将一个对象放入集合时，BloomFilter的多个独立哈希函数把同一对象映射到不同的Bit位，并将这些比特位置位；判断对象是否属于集合时，查找哈希函数映射到的bit位是否已经被置位过，如果没有被置位过，那么该元素一定不属于集合。但是，如果映射到的位全部都被置位过，该元素有可能不属于集合（false positive）。如果m表示bit个数，n表示已经放入BloomFilter的元素个数，k表示哈希函数的个数，那么元素被误判为属于集合的概率为公式一：

当k=ln2*(m/n)时，可以使误差概率最小，此时误差为公式二：

BloomFilter的实现

该实现中bit位个数m = 1 << 30(1073741824约10亿)，独立Hash函数的个数K为9，假设已插入的字符串个数n = 10000000（1千万）。则根据公式一，再次插入一个新字符串时，误判为字符串已存在的概率为1.4041653253261077E-10（10亿分之1.4）。根据公式二，此时最佳的K值为74.42611179548929。

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

class BloomFilter implements Serializable {
    private final int BITS_NUM = 1 << 30;
    private final int K_NUM = 9;
    private BitSet bits;
    private int[] seeds;
    private HashFunc[] hashs;

    private static final BloomFilter bloomFilter = new BloomFilter();

    private BloomFilter() {
        bits = new BitSet(BITS_NUM);
        seeds = new int[]{3, 5, 7, 11, 13, 17, 19, 23, 29};
        hashs = new HashFunc[K_NUM];
        for (int i = 0; i < K_NUM; ++i)
            hashs[i] = new HashFunc(seeds[i], BITS_NUM);
    }

    public static BloomFilter getBloomFilter() {
        return bloomFilter;
    }

    public boolean isIn(String s) {
        for(HashFunc hashFunc : hashs)
            if(!bits.get(hashFunc.hash(s)))
                return false;
        return true;
    }

    public void insert(String s) {
        System.out.println(bits);
        for(HashFunc hashFunc : hashs)
            bits.set(hashFunc.hash(s));
        System.out.println(bits);
    }
}

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

https://leetcode.com/problems/word-break-ii/

public List<String> wordBreak(String s, Set<String> dict) {
        List<String> result = new ArrayList<String>();
        if(s == null || dict == null ) return result;

        List<String>[] dp = new ArrayList[s.length() + 1];
        dp[0] = new ArrayList<String>();

        for(int i = 0; i < s.length(); ++i) {
            if(dp[i] == null) continue;
            for(String word : dict) {
                int len = word.length();
                if(i + len <= s.length() && word.equals(s.substring(i, i + len))) {
                    if(dp[i + len] == null)
                        dp[i + len] = new ArrayList<String>();
                    dp[i + len].add(word);
                }
            }
        }

        if(dp[s.length()] == null) return result;

        dfs(result, dp, new ArrayList<String>(), s.length());
        return result;
    }

    private void dfs(List<String> result, List<String>[] dp, List<String> list, int end) {
        if(end <= 0) {
            StringBuilder s = new StringBuilder();
            for(int i = list.size() - 1; i >= 0; --i) {
                if(i != list.size() - 1) s.append(' ');
                s.append(list.get(i));
            }
            result.add(s.toString());
            return;
        }

        for(String s : dp[end]) {
            list.add(s);
            dfs(result, dp, list, end - s.length());
            list.remove(list.size() - 1);
        }
    }