如果要对边进行排序，或按边的权重进行排序，推荐使用边集数组

基础理论

度：

对于无向图

背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。

背包问题有以下几种分类：

1. 01背包问题
2. 完全背包问题
3. 多重背包问题

回表查询

聚集索引的叶子节点包含完整的行数据，而非聚集索引的叶子节点存储的是每行数据的辅助索引键 + 该行数据对应的聚集索引键（主键值）。

假设有张 user 表，包含 id（主键），name，age（普通索引）三列，有如下数据：

摩尔投票算法基础理论及最佳实践

会议大厅站满了投票代表，每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的（所选的候选人不同）两个人，会打一架，并且会同时击倒对方。

这里意见不合的两个人促成了算法的核心思想：对拼消耗

MYSQL 索引选择性陷阱

场景：

用户表有1000个用户，其中有一个sex（性别）字段。sex字段上有一个sex索引。

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

1.延时双删

• 删除缓存
• 更新数据库
• sleep 500ms
• 删除缓存

2.读取mysql的binlog，订阅数据库更新日志。

分布式锁的实现方式

1 数据库乐观锁

利用表的唯一索引行级锁进行加解锁，加锁：