08｜外部排序：如何为TB级数据排序？

败者树和堆实现是相似的，量级上的复杂度也相同，具体有两点不同，第一，队列长度固定，第二，插入位置在叶节点。败者树是为多路归并量身定做的，效率应该更高，堆原来为了维护满二叉树的工作在多路归并中是不需要的。败者树和胜者树相比，树的中间节点记录的内容要更全，胜者树，胜出的元素会多次重复，这样中间节点的信息丢失，下一次比赛无法充分利用以前的比赛结果。败者树每个中间节点都记录了需要通关的门槛，而且不重复，一路比较即可。 基于线性排列的对任意文本可能会有点问题，如果都是字母单词应该可以，可以把单词按照首字母先分好文件，再按照第二个，递归排序。 1TB，假设内存是1G，分成1000个顺位文件，请问老师这里的归并路数可不可以直接选用1000，一次归并即可，因为归并的时候理论上内存只用存储树的节点数目（大约2000个）。

外部排序算法历史悠久，像基数排序甚至在电子计算机出现之前就被用来排序打孔卡。

有个问题没有理解，外部数据越归并越多了，每一次归并需要读入内存就越来越多，那还是会产生内存不足的问题？

算法题使用败者树实现-golang版本，参考C++版本写了半天感觉还是对败者树有点陌生~ ```go package main type ListNode struct { Val int Next *ListNode } type loserTree struct { tree []int leaves []*ListNode } var dummyVal = 100000 var dummyListNode = ListNode{Val: dummyVal} func New(leaves []*ListNode) *loserTree { k := len(leaves) if k & 1 == 1 { leaves = append(leaves, &dummyListNode) k++ } lt := &loserTree{ tree: make([]int, k), leaves: leaves, } if k > 0 { lt.init() } return lt } func (lt *loserTree) init() { lt.tree[0] = lt.getWinner(0) } func (lt *loserTree) getWinner(idx int) int { if idx == 0 { return lt.getWinner(1) } if idx >= len(lt.tree) { return idx - len(lt.tree) } left := lt.getWinner(idx*2) right := lt.getWinner(idx*2+1) if lt.leaves[left] == nil { lt.leaves[left] = &dummyListNode } if lt.leaves[right] == nil { lt.leaves[right] = &dummyListNode } if lt.leaves[left].Val < lt.leaves[right].Val { left, right = right, left } lt.tree[idx] = left return right } func (lt *loserTree) Pop() *ListNode { if len(lt.tree) == 0 { return &dummyListNode } treeWinner := lt.tree[0] winner := lt.leaves[treeWinner] lt.leaves[treeWinner] = winner.Next if lt.leaves[treeWinner] == nil { lt.leaves[treeWinner] = &dummyListNode } treeIdx := (treeWinner + len(lt.tree)) / 2 for treeIdx != 0 { treeLoser := lt.tree[treeIdx] if lt.leaves[treeLoser].Val < lt.leaves[treeWinner].Val { treeLoser, treeWinner = treeWinner, treeLoser } lt.tree[treeIdx] = treeLoser treeIdx /= 2 } lt.tree[0] = treeWinner return winner } func mergeKLists(lists []*ListNode) *ListNode { dummy := new(ListNode) pre := dummy lt := New(lists) for { node := lt.Pop() if node == &dummyListNode { break } pre.Next = node pre = node } return dummy.Next } ```

如果内存32G，其实 1TB的数据，是可以全部加载到内存的。malloc并没有实际分配内存，分配的都是虚拟内存，64位的虚拟内存远大于 1T，内存还可以和磁盘swap。

听这个课要具备怎样的基础啊，越来越听不懂了。感觉自己不适合做这一行。哭了哭了。

get了新知识

1、归并排序里，应该说明是在每个小文件做归并比较时，不是全部加入内存比较，而是文件首数据比较，然后生成到新文件里。 2、那个败者树和胜者树看起来不就是小顶堆、大顶堆的排序过程吗？但是这个败者排序中的图例写的并不对，你加入的节点8到底是winer还是loser啊。8是怎么和7比较变为loser8的啊。写的莫名其妙

其实要看吧，64位操作系统的虚拟内存是128TB，完全是可以直接读进来的。当然可能需要触发很多次的请求调页和页面置换。32位机的虚拟内存是3GB。好像没法直接读的

get了