8-2 学习总结

1. NP 问题：能在多项式时间内验证答案正确与否的问题；

1. 数组：连续内存空间，相同类型数据，查找时间复杂度 O（1）

1. 链表：零散内存空间，包含指向下一个数据元素内存地址的指针，查找的时间复杂度 O（N）

数组链表结合，实现快速查找增删

1. 哈希表：快速访问，快速删除；

1. stack：操作受限的线性表，LIFO

1. queue：操作受限的线性表，FIFO

1. BST =》 AVL =》 RedBlackTree

平衡二叉排序树：从任何一个节点出发，左右子树深度之差的绝对值不超过 1。

左右子树仍然为平衡二叉树。

红黑排序树：每个节点只有两种颜色，红色和黑色。

根节点为黑色；每个叶子节点都是黑色的空节点；从根节点到叶子节点，不会出现两个连续的红色节点。

从任何一个叶子节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

红黑树只需要三次旋转即可重新达到红黑平衡，时间复杂度 O（1）

大量增删的场景下，红黑树的效率更高。红黑树的平衡性不如平衡二叉树，查找效率略差。

1. hash 和 tree 在数据存储系统中的应用

1）hash 索引 - index for key-value data

所有的数据存在内存中，对于每个索引需要 snapshot 做备份，以防服务器 crash 导致索引恢复过慢；

缺点：范围查找效率低；数据量太大时，索引占用空间太大，内存占用太多，如果放到磁盘则随机 IO 会导致效率太低；

2）SortStringTables 和 LogStructuredMerge-Tree

使用 AVL 或者 RedBlackTree 用来在内存维护一个有序数据集，数据可以以任何数据写入，但是读出为有序数据。在存储系统中，一般这种 in-memory tree 称为 memtable；

当 memtable 大到一定阈值，通常为几 M，就会写入磁盘 SSTable 文件。这个过程很高效，因为读取红黑树的数据为有序集合。一般后台会有线程进行 SSTable 的合并，从而丢弃重复数据，减少存储空间；

同时为了防止系统 crash 导致 memtable 数据丢失，一般会有一个独立 log 去记录所有的写请求，例如 hbase 的 write ahead log，用于 crash 的恢复。当 memtable 写入 SSTable，则该 log 被替换删除；

但是，此类存储系统对于不存在数据的查询效率非常低，所以一般会结合 bloomfilter 用以提升性能；

3）B-Tree

B-Tree 和 SSTable 一样，维护一个有序 key-value pair，用以保证高效的 key 查询和范围查询；

但是他们有不同的设计哲学。

LSM Tree 索引是将数据拆分为不同的 segment，通常几 M 或更多；

而 B-Tree 则是将数据按 Page 或 Block（通常为 4K）读写。这种设计更贴近于硬件，因为磁盘就是基于固定的 block。

每一页数据都可通过地址标识，这样可以和其他页相互引用，从而组成一个 Page Tree 用于查找数据。

一般 B-Tree 需要 write-ahead log 或者说 redo log 来保证系统 crash 后的数据恢复。

一般而言，相比 B-Tree，LSM Tree 的写性能会更好，由于 SSTable 和 compaction 等问题，读性能会低于 B-Tree。