MySQL为何选择B+树存储索引

声明
本文所述的各种数据结构(二叉树等)，均不考虑重复值的情况，本文简述各种数据结构的区别仅仅只是为了理解MySQL索引的需要而做的铺垫。

什么是索引

提起索引，大家都知道，建立索引可以让数据库查询更快，那么索引究竟是什么？我想这就不是每个人都能说得出来了。
索引，是数据库管理系统中一个排序的数据结构，并用以协助快速查询、 更新数据库表中数据。
是的，索引是一种数据结构，但是那么多的数据结构中为何MySQL要选择B+树呢？接下来就让我们一起来了解下B+树相对于其他数据结构有何独特之处！

阅读全文»

[TOC]

一致性hash算法。用于解决memcached/redis 增减服务器时，尽量保持key依然命中之前的server的解决方案。

场景

假设我们有一个网站，最近发现随着流量增加，服务器压力越来越大，之前直接读写数据库的方式不太给力了，于是我们想引入Memcached作为缓存机制。现在我们一共有三台机器可以作为Memcached服务器，如下图所示。

阅读全文»

[TOC]

埃拉托斯特尼筛法求素数

算法

要得到自然数n以内的全部素数，必须把不大于 的所有素数的倍数剔除，剩下的就是素数。
给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去……。

阅读全文»

洗牌算法Fisher_Yates原理

[TOC]

算法

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

简单的原理如下图所示:

原理

总结下，洗牌算法Fisher_Yates的原理就是把从1到n的顺序候选集随机打乱，

做法就是

第1次从1-n的候选集合随机选个数，拿出此数，并把它从候选集合剔除(候选集合n-1)。

第2次从1-n-1的候选集合随机选个数，拿出此数，并把它从候选集合剔除(候选集合n-2)。

第2次从1-n-2的候选集合随机选个数，拿出此数，并把它从候选集合剔除(候选集合n-3)。

以此类推。

阅读全文»

雪花算法

[TOC]

唯一ID生成器snowflake

很多场景需要使用全局唯一ID，用来标识唯一一条消息，唯一一笔交易，唯一一个用户，唯一一张图片等等。
传统数据库表的自增主键是很简单的一种实现方式，前提是你没有分库，也没有分表，如果你分表了，id就会重复，失去唯一性：

阅读全文»

[TOC]

哈夫曼编码，为压缩而生。另有翻译为赫夫曼。

概念

哈夫曼树

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。

阅读全文»