1.SSTable的读写sstable文件由一个个块组成，按照顺序是数据区域，元数据区域，索引区域，尾部 生成块代码：table/block_builder.h和table/block_builder.cc 块中键值对存储其实根据前缀做了压缩，为shared_bytes+unshared_bytes+value_len+char[unshared_bytes]+char[value_len] add主要就存std::string buffer_;每次按照压缩后的格式添加 class BlockBuilder...

1.Memtable插入与查找位置在：db/memtable.h memtable类如下，主要方法是get、add和迭代器，其中迭代器事实上就是调用skiplist的迭代器这在下一节中说明 class MemTable { public: // MemTables are reference counted. The initial reference count // is zero and the caller must call Ref() at least once. explicit MemTable(const...

1.Log读写类位置在：db/log_writer.h、db/log_reader.h writer的构造函数传的是writablefile指针，就是上一篇文章讲到的，所以log读写类本质上只是定义了log格式 （7字节的header+变长record） class Writer { public: // Create a writer that will append data to "*dest". // "*dest" must be initially...

1.文件操作位置在：util/env_posix.cc （以posix系统为例，基类Env同样是虚类，PosixEnv是其具体实现，还有还有别的如Windows版本的） 注意文件读取在多环境下并不线程安全，需要开发者调用时采取外部手段 文件顺序读如下： read从文件当前位置读取指定字节数，skip为从当前位置跳过指定字节数 class PosixSequentialFile final : public SequentialFile { public: PosixSequentialFile(std::string filename, int fd) :...

1.数据库Open流程分析位置在：db/db_impl.cc 初始化dbimpl对象 尝试对dbimpl进行recover恢复 判断memtable是否为空（为空就创建新的log、memtable） 判断是否需要保存manifest文件，是就更新manifest 如果一切都成功，就删除过时文件尝试compaction操作 Status DB::Open(const Options& options, const std::string& dbname, DB** dbptr) { *dbptr =...

1.题干及思路给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。 如果 s 中存在多个符合条件的子字符串，返回任意一个。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 示例 1： 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最短子字符串...

一.剑指 Offer II 016. 不含重复字符的最长子字符串1.题干及思路给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。 示例 2: 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。 示例 3: 输入: s =...

一.剑指 Offer II 015. 字符串中的所有变位词1.题干及思路给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 变位词 指字母相同，但排列不同的字符串。 示例 1: 输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。 起始索引等于 6 的子串是...

一.剑指 Offer II 014. 字符串中的变位词1.题干及思路给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。 示例 1： 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 示例 2： 输入: s1= "ab" s2 =...

一.剑指 Offer II 013. 二维子矩阵的和1.题干及思路给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。 示例...