前言

最近研究比特币原理的时候，看到涉及的需求技术领域的实现方案，顺藤摸瓜，摸出许多的技术方案来需要问题和需求，开个帖子记录下所有的涉及的技术点，以及摸瓜情况

• levelDB
  google的一个采用lsm（log-structured merge tree）算法的db实现。它的特点是，写入速度非常快，读取速度相对而言不是优势项。写入快的原因是，该算法利用的磁盘顺序写入远高于随机写入的特性，采用log记录日志类似的方式，让所有数据的crud都顺序的以log的方式记录在文件中，以实现最快的写入速度。
  leveldb的实现方式中，有一个合并不同level的文件的策略，在合并文件的时候使用的是多路归并排序。

  • 多路归并排序
    多路归并排序是外部排序算法中常用的算法，其算法思想是，基于归并排序，把外部文件分成k个组，对每个组采用归并排序，然后对k个组的第一个元素进行排序处理，结果放到结果队列中。直到所有组的处理完毕。
    多路归并排序，会随着组数k的增加，而降低效率。因为对k个组的数据进行处理时，要循环的次数会显著的增加，这个时候可以使用胜者树或者败者树来减低时间的复杂度，达到提升效率的目的。
    该排序算法应用的场景是，数据量巨大，内存有限的场景。

  • 归并排序
    归并排序的思想是把一个数组细分成一个一个的元素，然后对元素两两排序，然后再对第一次排序好的两个元素一组的两组元素分别排序，然后对4个元素一组的两两排序，直到排序完毕。

  • 外部排序算法
    外部排序算法应对的主要是，待排序的文件在磁盘中，而且较大，此时需要一种机制从磁盘中读取数据，然后在有限的内存中排序。上面介绍的多路归并排序就是其中的一种。还有位图排序等。待更新。

  • 位图排序
    位图排序算法的思想是，对于一组不重复的有限大小的正整数，采用bit位来记录数，比如{1，5，4，8}这个数据，用bit位记录为 010011001000,即从左到右第1位，第4位，第5位，第8位都为1。这样就达到了排序的目的。

  • 计数排序
    计数排序比较适合待排序数据比较集中的场景，数据太分散，对于排序的空间复杂度会大大增加。
    计数排序的思想是，类比下现实中的一个场景，假如一个班级的童鞋要按高矮个排队，每个童鞋只要知道比自己矮的童鞋有多少个，就能找到自己的位置，对号入座了。假如有身高相同的童鞋，则需要此身高排最后的童鞋把前面几个相同身高的童鞋也算进去来计算自己的排位。
    实现思路：设计3个数据a[]，b[]，c[],a[]表示原数据，b[]表示结果数据，c[]表示中间数据。排序的数据为0-k的整数

    • 初始化c[0...k]为0
    • 对于i=0..n-1 ，c[a[i]]++，c中存储了所有数的个数，比如{1，1，3，5}最后为c[1]=2，c[3]=1，c[5]=1
    • 对于i=1...k，c[i] = c[i]+c[i-1]，计算所有c[i]前总共有多少个数
    • 对于i=n-1...0，b[c[a[i]]]=a[i],a[i]--;最后的a[i]--用来处理重复数据的问题，从后向前便利保证排序算法的稳定性

  • 桶排序 bucket sort
    桶排序也是一种非比较排序，计数排序，基数排序，位图排序都是非比较排序。桶排序的思想是，把数据按照一定的散发比例，分到几个桶中，然后在桶中分别进行排序，然后再合并桶中的数据。比如0...n的数据分布在m个桶中，每个桶中含有的数据段范围为，n/m,然后针对每个m里面的数据进行排序。
    桶排序有两种情况

    1. 当桶划分的非常均匀的时候，即每个桶分到了一个数据，这个时候不需要排序，合并桶就能达到排序的目的，时间复杂度就是logN
    2. 当然也有反例，当数据分散的不是很均匀，这种情况下，桶排序的效果就体现不出来。
       所以，桶排序适合相对均匀分布的数据源

  • 基数排序 radix sort
    基数排序实际上是一种多种排序方式的应用，是一种多关键字的排序，适用的场景举例：扑克牌的排序，先根据花色，然后再根据大小排序；班级成员，先根据姓名，再根据年龄和成绩排序。等等。
    排序的基本思想是，分别针对每个关键字进行排序。例如{332，342，234，123，531}，先对个位排序，再对十位排序，最后对百位排序；或者，倒过来，先对百位排序，然后十位，然后个位。
    由小到大的顺序叫做lsd方法，（least significant digital）；由大到小的顺序叫做msd方法，（most significant digital）。
    lsd方法，在关键字不多时效率很高，此方法需要使用的排序算法是稳定的。
    msd方法，在关键字多时表现的较好，不过空间损耗相应的会变大。
    相比于桶排序，基数排序出场的几率更高些。

  • 样本排序sample sort
    样本排序是并行的桶排序，使用分布式的方式对外部数据排序，是一种常用的外部排序方式。google使用的排序方式。基本的思路是，首先要解决桶排序的数据均分问题，解决了数据均分问题后，再把分解的各个桶，分给多个线程处理，最后合并。
    假设数据源为1...n，我们要分为m份数据（即有m个桶），使用p个线程处理这些数据，让p=m，基本方法是：根据m，把n分为m份数据，每份数据含有n/m个数据，分别对这些数据进行快速排序，然后在排序结果中取m-1个均匀分布的数，这样最后会得到m*(m-1)个数。实际执行过程是，每个线程p，分别处理这些n/m数据，然后把m-1个数据发送给一个特殊线程p0，p0把这些数重新排序，然后取出m-1个均匀分布的数，作为splitter。