个人备案能做什么网站/数据分析师35岁以后怎么办

1. 写在最前面

1.1 背景

这篇文章产生的原因是，我去请教某位同学 LevelDB 的使用场景，经典对话如下：

大佬：那你觉得 LevelDB 解决了啥问题？(ps：就挺突然，一个反问，问的我措手不及，不要你觉得要我觉得

我：对比同类型的 K/V 存储的话，LevelDB 实现使用了 LSM Tree 写入的速度会更快

大佬：为啥？

我：查网络上资料是 LSM Tree 会把磁盘的随机写变为顺序写，所以更快

大佬：上面是 LSM Tree 和 B 树对比的结果么，那有了 B 树为啥还要 LSM Tree？

注：我暗戳戳的质疑了一下，为啥要拿 K/V 存储的数据结构 LSM Tree 和关系型存储的数据结构 B 树对比，然后甩了 https://github.com/boltdb/bolt 这个给我，嗯，是 B+ Tree 实现的 K/V 存储，脸真疼

1.2 思考

通过这个问题，我又一次深深的意识到我跟大佬之间的差距了，嗯，可能得有一个珠穆朗玛峰吧

• 「抽象问题的能力」——抽象出重点， 换成问 LSM Tree 数据结构的使用场景？（抽象思维

  • 比如，虽然问的原始问题是 LevelDB 的使用场景？

    但是其实有很多的变种，比如可以问 RocksDB 的使用场景？

    如果能抽取两者的共性，分析 LSM Tree 数据结构的使用场景，则是更优的解决问题的思路。

    注：RocksDB 和 LevelDB 的实现均使用 LSM Tree

• 「总结问题的能力」—— 由一个问题推导一类问题甚至更多？（举一反三思维

  • 比如，LSM Tree 和 B 树都可以被用做索引，而索引这个概念我们大部分人都知道。但是深入来问呢？

    • 为什么要加索引？

    • 加了索引可以解决什么问题？

    • 索引可用什么数据结构？

    • ……

    我们所不知道的知识有很多且无法尽数枚举，但是在面对那些我们不知道知识时，学会使用举一反三能力阔以事半功倍吖

    注：道生一，一生二，二生三，三生万物。

2. 索引为了解决什么问题

2.1 为什么要加索引

在回答这个问题前，先让我们来分析一下下图。老规矩，还按照「自低向上，逐级深入」的方式。

1. 在只有几条数据的时候需要关心索引嘛？

   答：不需要，但不需要不代表不能够，所以意味着此处仍有多种选择。
   a. 直接链表或者数组存储，需要的时候全局遍历

   ​ b. 用树存储或者有序数组存储，需要的时候二分查找

2. 那数据量增到几千、几万甚至十万条呢？

   答：不一定，看场景，视数据集里记录的大小而定

3. 那数据量增加到几亿条且记录大小均在 4M 左右呢？

   答：要，不然这个体量的数据全局遍历查找，你要么被老板 fire，要么被用户寄刀片

综上所述，加索引的目的就显而易见了。

在数据增加到一定体量的情况下，加索引能够帮助我们更快速的搜索数据。

思考：所以全表扫描一定会比走索引慢嘛？

2.2 索引的本质

索引的本质（ps 以下这段话，我学习的时候无比震惊

将 IO 操作转成 CPU 操作，把内存操作转成 cache 操作，把低速介质的访问转成对高速介质的访问，减少对低速介质的依赖。

通过高速介质的缓存效果，index 比 data 小，而且有序，可以快速逼近，整个操作由 CPU 尽量在内存中完成，避免 io 介入，所以 io -> cpu & mem，CPU 完成逼近，mem 完成数据传输与缓存，尽可能减少 io

注：初次听的时候，总觉得这个理论不对劲，但是听着听着觉得，有种惊为天人的感觉，原来还能这么理解

给出两组数组，一组为有序数组，一组为无序数据，遍历找到其中元素值为 9 的元素，如下图所示，对比下两种方式得到如下几点结论：

• 查找次数代表着查找速度的快慢
• 随着数据量的增加，这两种方式的查找速度呈现出巨大的差距 O(n) vs O(log(n))

2.2.1 论加索引

首先，实际的生产环境中，数据的产生必然具有无序，随机的特性。

其次，而为了能够快速查询到数据，这就要求我们在存储数据的时候，就按照有序的方式存储。

然后，为了能够更加快速的抽象出数据记录，可以显示的选择记录的字段或者隐式生成一个 id，作为索引代表整条记录，好处是提高了查询速度的同时，压缩了数据规模。（ps 比如 mysql 的索引一般建议选择自增 id

最后，以上就是索引的概念总结。

一图胜千言，感受下加索引的重要性。（ps 年少不知索引好，错把全扫当真爱……

3. 索引的数据结构对比

下图中列举的数据结构均可被用来做索引，但请注意这里是个子集关系（即除下图所列还有其他的数据结构

思考🤔：不要自己拿着一个锤子，就看啥都像钉子。

提起索引就 B+ 树，你让红黑树和 LSM Tree 的脸往哪里放吖。

3.1 更快的查找啥？

好了，至此为止，已经知道索引能够加速查找过程了，那么是加速什么的查找过程呢？

• 等值查找
• 范围查找
• 模糊查找
• 差值查找
• 总和查找
• ……

反正查找选择千变万化，看自己的业务需要的是哪种，然后选择一种数据结构即可。

3.2 B+ vs LSM 树

既然说的一直是本质，这里也直接上本质。所以基础的概念这里就不写了，「好奇心跟笔者一样的同学」可以猛戳下面的参考资料。

3.2.1 B+ 树

B+ 树的本质是可插入的有序 Array。

• 缺点是：array 变换成了 tree 结构，导致插入需要 search，所以 B+ 树的弱在插入，因为插入的前置代价是找到位置
• 优点是：查询速度快

注：B+ 树的问题是，insert 需要查找，node 满导致分裂，分裂需要持有非常大粒度的锁

3.2.2 LSM 树

LSM 树的本质是不可插入的有序 Array

• 缺点是：数据不可插入，只能通过merge来做，变成了logging，由此引入的连锁问题有，多层次引入写放大，merge cpu 成本极高，delete 操作被迫引入多版本，查找非常复杂。
• 优点是：写入速度快

3.2.3 Bw-tree

「学二送一，学到就是赚到」

Microsoft 的 DocumentDB，即现在的 Azure Cosmos DB 背后基于Bw-Tree。Bw-tree 的本质是叶子节点的 append 替代分裂，代价是额外的元数据管理。

• LSM 树是为了写
• Bw-tree 是为了并行，把某个节点的 buffer 操作原子化，避免锁。

注：前置知识，点包括段

并发是时间段，时间段内同时执行

并行是时间点，时间点同时执行

这个更深层次的还涉及全序和偏序的概念，嗯，一切皆数学……

注：Bw-tree 笔者也不是很了解，后面单独写一篇文章来学习好啦，此处仅做记录，这部分可以跳读

4. 碎碎念

免责声明，以上均为笔者自己的想法跟思考，有错误欢迎指出。

• 好在沮丧很多的时候小幸福也很多，因为天气很好，因为吃到了好吃的零食，因为周末可以悄悄睡个懒觉，为很多小小的满足感到温暖开心。
• 因为知识越贫乏，你所相信的东西就越绝对，因为你根本没有听过与此相对立的观点。夜郎自大是无知者，和好辩者的天性。

是没有拖延，月初完结撒花的一天，晚上可以吃草莓啦

5. 参考资料

• System Properties Comparison LevelDB vs. Redis vs. RocksDB
• Difference between O(n) and O(log(n)) - which is better and what exactly is O(log(n))?
• 你见过最烂的代码长什么样子
• MySQL 索引结构
• Bw-tree技术解读
• 深入理解 Mysql 索引底层数据结构与算法
• AVL 树