归并排序

SSTables 通过按照键的顺序存储在日志段文件中来解决哈希索引面临的一些问题。它要求每个键在每个合并的段文件中只能出现一次（通过压缩确保）。 对比哈希索引的日志段 优点 合并段更加高效，即使文件大于可用内存。类似于归并排序算法中使用的方法。并发读取多个输入段文件，比较每个文件的第一个键，把最小的键拷贝到输出文件，并重复。 解决多个段文件重复：保留最新的值，因为每个段包含在某段时间内写入数据库的所有值，意味着肯定有一个值比其他所有值更新。 基于键有序的特性可以采用稀疏索引避免内存中包含所有键的索引。 将一定范围内的所有键存储到一个块中，便于需要请求范围内多个 key-value，降低磁盘 I/O。 构建和维护 保证顺序 内存中痛哦红黑树或者 AVL 树支持任意顺序插入并以排序后的顺序读取它们。 写入时，将其添加到内存中的平衡树数据结构中，成为内存表。 内存表大于某个阈值（MB级别），将其作为 SSTable 文件写入磁盘。写入同时，写入可以继续添加到一个新的内存表实例中。 处理请求顺序：首先从内存表中查找键 -> 最新的磁盘段文件 -> 次新磁盘段文件，以此类推。 后台进程周期性执行段合并与压缩，合并多个段文件并丢弃被覆盖或着删除的值。 崩溃处理 为了避免数据库崩溃最近的写入（在内存表中尚未写入磁盘）将会丢失的问题： 在磁盘上保留单独的日志，每个写入都会立即追加到该日志。并且无需排序。 内存表写入 SSTable 时，丢弃相应的日志。 使用此技术的数据库 LevelDB RocksDB 类似的 Cassandra HBase

tags: LeetCode 思路 归并排序 代码 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { nums := mergeSort(nums1, nums2) length := len(nums) if length % 2 != 0 { return float64(nums[(length - 1) / 2]) } i := length / 2 return (float64(nums[i]) + float64(nums[i - 1])) / 2 } func mergeSort(nums1 []int, nums2 []int) []int { l1 := len(nums1) l2 := len(nums2) result := make([]int, 0, l1 + l2) i, j := 0, 0 for i < l1 && j < l2 { if nums1[i] < nums2[j] { result = append(result, nums1[i]) i++ } else { result = append(result, nums2[j]) j++ } } result = append(result, nums1[i:]...) result = append(result, nums2[j:]...) return result }