使用 Vue 实现一个虚拟列表

大列表问题

因为 DOM 性能瓶颈，大型列表存在难以克服的性能问题。因此，就有了 “局部渲染” 的优化方案，这就是虚拟列表的核心思想。

虚拟列表的实现，需要重点关注的问题一有以下几点：

可视区域的计算方法
可视区域的 DOM 更新方案
事件的处理方案

下面逐一分解说明。

可视区域计算

可视区域的计算，就是使用当前视口的高度、当前滚动条滚过的距离，得到一个可视区域的坐标区间。算出可视区域的坐标区间之后，在去过滤出落在该区间内的列表项，这个过程，列表项的坐标也是必须能算出的。

思考以下情况，

我们的视口高度为 100px
我们当前已经滚动了 100px
我们的列表项，每一项高度为 20px

根据这些条件，我们可以计算出，当前可视区域为第 11 项至第 20 项。

  01 - 05，可视区域上方
+----+-----------+--------
| 06 | 100 ~ 120 |
+----+-----------+
| 07 | 120 ~ 140 |
+----+-----------+
| 08 | 140 ~ 160 | 可视区域
+----+-----------+
| 09 | 160 ~ 180 |
+----+-----------+
| 10 | 180 ~ 200 |
+----+-----------+--------
  11 - N，可视区域下方

这是因为列表项高度是固定的，我们可以通过简单的四则运算算出已经滚动过去的 100px 中，已经滚动走了 5 个列表项，因此可视区域是从第 6 项开始，而视口高度为 100px，能容纳 100 / 20 即 5 个条目。

上面例子的情况非常简单，也不存在性能问题，因此实际上并没有展开讨论的价值。而还有另一种复杂很多的情况，那就是，列表项高度不固定，根据内容决定高度。

此时，我们就没办法直接使用四则运算一步到位算出可视区域对应的条目了。

而必须实现一种机制，记录所有列表项的坐标，再通过检查列表项是否落在视口内。

下面重点讨论该问题。

列表项的坐标

列表项的坐标，可以通过以下公式定义：

<列表项 top 坐标值> = <上一项 top 坐标值> + <上一项的高度值>

第一个列表项的 top 坐标值为 0，因此，只要记录所有列表项目的高度，即可算出任意一个列表项的 top 坐标值。于是，问题就变成了，必须使用某种方式来存储每个条目的高度。

我想，最容易想到的方案就是，使用一个数组，一一对应地存储列表每项的高度值。然后获取特定项的坐标值时，提取第一项到目标项的值，进行累加运算。参考下面代码进行理解：

// 假设使用该数组存储列表每一项的高度
const itemHeightStore = [20, 20, 20, 20, 20]

// 使用该方法，可以算出列表中指定项的 top 坐标值
const getTop = (index) => {
  let sum = 0
  while (index--) sum += itemHeightStore[index] || 0
  return sum
}

// 第一项
getTop(0) // 0

// 第二项
getTop(1) // 20
// ...

该实现可以很好地工作。

但是，该算法存在严重的性能问题，每获取一个列表项的坐标都要遍历列表，复杂度 O(n)，非常不划算。

如果换一种方式，直接存储每一项的坐标呢？

其实本质是一样的。因为我们的列表项高度是不固定的，我们快速拖动滚动条到不同的区域时，需要根据局部渲染结果算出高度用于更新数组记录，而在更新某一项时，该项后续的所有条目也需要全部更新，复杂度一样是 O(n)。

所以，使用数组来维护每一项的高度或者坐标，在列表规模比较大的时候，就会消耗大量的 CPU 时间。

也许使用 TypedArray 会有好的表现？

仔细观察上面例子中的数组，结合现实中列表的情况，我们可以观察到一个现象：

列表项往往是相似的，在许多情况下，高度也很可能是一致的。

基于这种经验，我们可以采用区间来存储列表项的高度。

通过折叠记录相邻的，相同高度的列表项，来减少列表遍历操作。

比如以下表示方式：

const range = {
  start: 0,
  end: 4,
  value: 20
}

可以很好地表达列表第 1 项至第 5 项的高度都为 20px。

如果我们需要求第 6 项的高度的话，就只需进行一次简单的四则运算即可，无需遍历累加这 5 项。

很容易得出结论，如果列表大部分情况是相同高度，只有个别条目高度不一致时（例如文本换行），将会有非常优异的性能表现。

当然使用区间，也不是没有代价的。这又会带来数据结构的复杂性。

由于折叠了相邻相同高度的结点，会导致存储的列表无法跟原始条目一一对应。所以，我们就不能简单得知我们想查询的列表项的高度存储在哪里了，为此需要设计一种专门的存储机制。

这种存储机制，需要拥有这些特性：

高效的查询。可以通过列表项序号，快速获得对应的 range，以及该 range 之前的所有 range。
高效地修改。可以高效地插入、移除 range，合并 range、拆分 range。

结合我们学过的数据结构知识，可以考虑使用某种 BST 来存储，从而获得良好的查询、插入性能。而 range 的合并、拆分等，则可以实现一个专门的类来管理。

下面直接给出一个简单的代码实现供参考，代码中已经加上了大量的注释，直接阅读应该比解说要更清晰。

// Avl.ts
const SLIGHTLY_UNBALANCED_RIGHT = -1
const SLIGHTLY_UNBALANCED_LEFT = 1
const UNBALANCED_RIGHT = -2
const UNBALANCED_LEFT = 2

// 树结点
class AvlNode<K extends any = any> {
  key: any
  left: AvlNode<K> | null
  right: AvlNode<K> | null
  parent: AvlNode<K> | null
  _height: number
  _prevHeight: number

  constructor(key: K) {
    this.key = key
    this.left = null
    this.right = null
    this.parent = null
    this._height = 0
    this._prevHeight = 0
  }

  // 刷新前的高度，方便平衡操作
  get prevHeight() {
    return this._prevHeight | 0
  }

  get height() {
    return this._height | 0
  }

  set height(value) {
    this._prevHeight = this._height | 0
    this._height = value | 0
  }

  // 左子树高度
  get leftHeight() {
    if (this.left === null) return -1
    return this.left.height | 0
  }

  // 右子树高度
  get rightHeight() {
    if (this.right === null) return -1
    return this.right.height | 0
  }

  // 平衡因子
  get balanceFactor() {
    return this.leftHeight - this.rightHeight
  }

  updateHeight() {
    const { leftHeight, rightHeight } = this
    const height = ((leftHeight > rightHeight ? leftHeight : rightHeight) + 1) | 0
    this.height = height
  }
}

// AVL 树
export class Avl<K extends any = any> {
  _root: AvlNode<K> | null
  _size: number

  constructor() {
    this._root = null
    this._size = 0
  }

  get size() {
    return this._size
  }

  // 插入节点
  insert(key: K) {
    const node = new AvlNode<K>(key)
    const insertPoint = this._nodeInsert(node)

    // 本次插入是重复结点，直接更新 key / value
    // 无新结点插入，所以无需进行插入后的调整
    if (insertPoint == null) return

    // 新增结点成功时，回溯调整搜索路径上的结点
    this._adjustAfterInsertion(insertPoint)
  }

  // 删除节点，返回是否成功删除结点
  delete(key: K): boolean {
    // 搜索待删除结点
    const targetNode = this._nodeSearch(key)
    // 未找到 value 对应结点
    if (targetNode == null) return false

    // 执行删除结点操作
    const backtracking = this._nodeErase(targetNode)
    const parent = backtracking[0]

    // 回溯调整搜索路径上的结点
    if (parent !== null) {
      this._adjustAfterRemoval(parent)
    }

    return true
  }

  // 通过 key 查找包含该 key 范围的节点 key
  search(key: K) {
    const node = this._nodeSearch(key)
    if (node !== null) return node.key
    return null
  }

  // 搜索 start 、end 两个 key 之间的所有 key 列表
  searchRange(start: K, end: K) {
    const results: K[] = []

    // 找到符合条件的 root 节点
    let root = this._root
    while (root !== null) {
      const result1 = start.compareTo(root.key)
      const result2 = end.compareTo(root.key)
      // 当前节点比 start 小，不再搜索左子树
      if (result1 > 0) {
        root = root.right
        continue
      }
      // 当前节点大于 end，不再搜索右子树
      if (result2 < 0) {
        root = root.left
        continue
      }
      break
    }
    if (!root) return results

    const stack = []
    let current: AvlNode<K> | null = root
    while (stack.length || current) {
      while (current) {
        stack.push(current)
        // 当前节点比 start 小，不再搜索 current 的左子树
        if (start.compareTo(current.key) > 0) break
        current = current.left
      }
      if (stack.length) {
        // 指向栈顶
        current = stack[stack.length - 1]
        const gteStart = start.compareTo(current.key) <= 0
        const lteEnd = end.compareTo(current.key) >= 0
        if (gteStart && lteEnd) {
          results.push(current.key)
        }

        stack.pop()

        // 只有 current 比 end 小，才继续搜索 current 的右子树
        if (lteEnd) {
          current = current.right
        }
        else {
          current = null
        }
      }
    }
    return results
  }

  // 增加结点数量
  _increaseSize() {
    this._size += 1
  }

  // 减少结点数量
  _decreaseSize() {
    this._size -= 1
  }

  // 设置左子结点，同时维护 parent 关系
  _setLeft(node: AvlNode<K>, child: AvlNode<K> | null) {
    // 断开旧 left 结点
    if (node.left !== null) {
      node.left.parent = null
    }
    // 连接新结点
    if (child !== null) {
      // 从旧 parent 中断开
      if (child.parent !== null) {
        child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
      }
      child.parent = node
    }
    node.left = child
  }

  // 设置右子结点，同时维护 parent 关系
  _setRight(node: AvlNode<K>, child: AvlNode<K> | null) {
    // 断开旧 right 结点
    if (node.right !== null) {
      node.right.parent = null
    }
    // 连接新结点
    if (child !== null) {
      // 从旧 parent 中断开
      if (child.parent !== null) {
        child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
      }
      child.parent = node
    }
    node.right = child
  }

  // 获取中序遍历顺序的前驱结点
  _inorderPredecessor(node: AvlNode<K> | null) {
    if (node == null) return null

    // 1. 有左子树，找到左子树最大元素
    if (node.left !== null) {
      return this._maximumNode(node.left)
    }

    // 2. 没有左子树，往上搜索
    let parent = node.parent
    while (parent != null) {
      if (node == parent.right) {
        return parent
      }
      node = parent
      parent = node.parent
    }

    // 4. 搜索到根
    return null
  }

  // 获取最大的结点
  _maximumNode(subRoot: AvlNode<K>) {
    let current = subRoot
    while (current.right !== null) current = current.right
    return current
  }

  // 设置根结点
  _setRoot(node: AvlNode<K> | null) {
    if (node === null) {
      this._root = null
      return
    }
    this._root = node
    // 如果本身在树中，则从树中脱落，成为独立的树根
    if (node.parent !== null) {
      node.parent.left === node ? (node.parent.left = null) : (node.parent.right = null)
      node.parent = null
    }
  }

  // 将树上某个结点替换成另一个结点
  private _replaceNode(node: AvlNode<K>, replacer: AvlNode<K> | null) {
    if (node === replacer) return node

    // node 为 root 的情况
    if (node === this._root) {
      this._setRoot(replacer)
    }
    else {
      // 非 root，有父结点的情况
      const parent = node.parent as AvlNode<K>
      if (parent.left === node) this._setLeft(parent, replacer)
      else this._setRight(parent, replacer)
    }

    return node
  }

  // 左旋，返回新顶点，注意旋转完毕会从原本的树上脱落
  private _rotateLeft(node: AvlNode<K>) {
    const parent = node.parent
    // 记录原本在树上的位置
    const isLeft = parent !== null && parent.left == node

    // 旋转
    const pivot = node.right as AvlNode<K>
    const pivotLeft = pivot.left
    this._setRight(node, pivotLeft)
    this._setLeft(pivot, node)
    // 旋转完毕

    // 新顶点接上树上原本的位置
    if (parent !== null) {
      if (isLeft) this._setLeft(parent, pivot)
      else this._setRight(parent, pivot)
    }

    // ---
    if (node === this._root) {
      this._setRoot(pivot)
    }

    node.updateHeight()
    pivot.updateHeight()

    return pivot
  }

  // 右旋，返回新顶点，注意旋转完毕会从原本的树上脱落
  private _rotateRight(node: AvlNode<K>) {
    const parent = node.parent
    // 记录原本在树上的位置
    const isLeft = parent !== null && parent.left === node

    // 旋转
    const pivot = node.left as AvlNode<K>
    const pivotRight = pivot.right
    this._setLeft(node, pivotRight)
    this._setRight(pivot, node)
    // 旋转完毕

    // 新顶点接上树上原本的位置
    if (parent !== null) {
      if (isLeft) this._setLeft(parent, pivot)
      else this._setRight(parent, pivot)
    }

    // ---
    if (node === this._root) {
      this._setRoot(pivot)
    }

    node.updateHeight()
    pivot.updateHeight()

    return pivot
  }

  // 搜索 Node
  private _nodeSearch(key: K) {
    let current = this._root
    while (current !== null) {
      let result = key.compareTo(current.key)
      if (result === 0) return current
      if (result < 0) current = current.left
      else current = current.right
    }
    return null
  }


  // 在树里插入结点或者刷新重复结点
  // 返回新插入（或刷新）的结点
  private _nodeInsert(node: AvlNode<K>) {
    // 空树
    if (this._root === null) {
      this._setRoot(node)
      this._increaseSize()
      return null
    }

    const key = node.key
    let current = this._root

    // 查找待插入的位置
    while (true) {
      const result = key.compareTo(current.key)
      if (result > 0) {
        if (current.right === null) {
          this._setRight(current, node)
          this._increaseSize()
          return current
        }
        current = current.right
      }
      else if (result < 0) {
        if (current.left === null) {
          this._setLeft(current, node)
          this._increaseSize()
          return current
        }
        current = current.left
      }
      else {
        // No duplicates, just update key
        current.key = key
        return null
      }
    }
  }

  // 从树上移除一个结点
  private _nodeErase(node: AvlNode<K>) {
    // 同时拥有左右子树
    // 先转换成只有一颗子树的情况再统一处理
    if (node.left !== null && node.right !== null) {
      const replacer = this._inorderPredecessor(node)!

      // 使用前驱结点替换身份
      // 此时问题转换成删掉替代结点（前驱），
      // 从而简化成只有一个子结点的删除情况
      node.key = replacer.key

      // 修改 node 指针
      node = replacer
    }

    // 删除点的父结点
    const parent = node.parent

    // 待删结点少于两颗子树时，使用子树 (或 null，没子树时) 顶替移除的结点即可
    const child = node.left || node.right
    this._replaceNode(node, child)
    this._decreaseSize()

    return [ parent, child, node ]
  }

  // AVL 树插入结点后调整动作
  // 自底向上调整结点的高度
  // 遇到离 current 最近的不平衡点需要做旋转调整 
  // 注意: 对最近的不平衡点调整后 或者 结点的高度值没有变化时
  // 上层结点便不需要更新 
  // 调整次数不大于1
  _adjustAfterInsertion(backtracking: AvlNode<K> | null) {
    let current = backtracking
    // 往上回溯，查找最近的不平衡结点
    while (current !== null) {
      // 更新高度
      current.updateHeight()

      // 插入前后，回溯途径结点的高度没有变化，则无需继续回溯调整
      if (current.height === current.prevHeight) break

      // 若找到不平衡结点，执行一次调整即可
      if (this._isUnbalanced(current)) {
        this._rebalance(current)
        // 调整过，则上层无需再调整了
        break
      }

      current = current.parent
    }
  }

  // AVL树删除结点后调整动作
  // 自底向上调整结点的高度
  // 遇到离 current 最近的不平衡点需要做旋转调整
  // 注意: 对最近的不平衡点调整后，其上层结点仍然可能需要调整
  // 调整次数可能不止一次
  _adjustAfterRemoval(backtracking: AvlNode<K> | null) {
    let current = backtracking
    while (current !== null) {
      // 更新高度
      current.updateHeight()
      // 删除前后，回溯途径结点的高度没有变化，则无需继续回溯调整
      if (current.height === current.prevHeight) break

      if (this._isUnbalanced(current)) {
        this._rebalance(current)
      }

      // 与插入不同，调整过后，仍然需要继续往上回溯
      // 上层结点（若有）仍需判断是否需要调整
      current = current.parent
    }
  }

  // LL
  _adjustLeftLeft(node: AvlNode<K>) {
    return this._rotateRight(node)
  }

  // RR
  _adjustRightRight(node: AvlNode<K>) {
    return this._rotateLeft(node)
  }

  // LR
  _adjustLeftRight(node: AvlNode<K>) {
    this._rotateLeft(node.left!)
    return this._rotateRight(node)
  }

  // RL
  _adjustRightLeft(node: AvlNode<K>) {
    this._rotateRight(node.right!)
    return this._rotateLeft(node)
  }

  // 检查结点是否平衡
  _isUnbalanced(node: AvlNode<K>) {
    const factor = node.balanceFactor
    return factor === UNBALANCED_RIGHT || factor === UNBALANCED_LEFT
  }

  // 重新平衡
  _rebalance(node: AvlNode<K>) {
    const factor = node.balanceFactor
    // Right subtree longer (node.factor: -2)
    if (factor === UNBALANCED_RIGHT) {
      let right = node.right!
      // RL, node.right.factor: 1
      if (right.balanceFactor === SLIGHTLY_UNBALANCED_LEFT) {
        return this._adjustRightLeft(node)
      }
      else {
        // RR, node.right.factor: 0|-1
        // 即 right.rightHeight >= right.leftHeight
        return this._adjustRightRight(node)
      }
    }
    else if (factor === UNBALANCED_LEFT) {
      // Left subtree longer (node.factor: 2)
      let left = node.left!
      // LR, node.left.factor: -1
      if (left.balanceFactor === SLIGHTLY_UNBALANCED_RIGHT) {
        return this._adjustLeftRight(node)
      }
      else {
        // LL, node.left.factor: 1 | 0
        // 即 left.leftHeight >= left.rightHeight
        return this._adjustLeftLeft(node)
      }
    }
    return node
  }
}

export function createAvl() {
  return new Avl()
}

// SparseRangeList.ts

import { createAvl, Avl } from './Avl'

// 区间类
class Range {
  start: number
  end: number

  constructor(start: number, end?: number) {
    this.start = start
    this.end = end || start
  }

  // 用于 Avl 中节点的比较
  //
  // 列表中项目范围是连续的，必定不会重叠的
  // 如果传入的 key 为重叠的，则意味着希望通过构造一个子 Range 搜索所在的 RangeValue
  // 例如构造一个 { start: 10, end: 10, value: 'any' }，搜索树中
  // 范围包含 10~10 的 RangeValue，如 { start: 0, end: 20, value: 'any' }
  compareTo(other: Range) {
    if (other.start > this.end!) return -1
    if (other.end! < this.start) return 1
    return 0
  }
}

// 区间-值 类
class RangeValue<T> extends Range {
  value: T

  constructor(start: number, end: number, value: T) {
    super(start, end)
    this.value = value
  }

  clone(): RangeValue<T> {
    return new RangeValue(this.start, this.end!, this.value)
  }
}

// 最终存储区间-值的类，内部使用 Avl 存储所有 RangeValue
export default class SparseRangeList<T> {
  _size: number
  defaultValue: T
  valueTree: Avl

  constructor(size: number, defaultValue: T) {
    this._size = size
    this.defaultValue = defaultValue
    this.valueTree = createAvl()
  }

  get size() {
    return this._size
  }

  resize(newSize: number) {
    newSize = newSize | 0

    // 无调整
    if (this._size === newSize) return

    // 扩容
    if (this._size < newSize) {
      this._size = newSize
      return
    }

    // 缩小，清空超出的部分，再缩小
    this.setRangeValue(newSize - 1, this._size - 1, this.defaultValue)
    this._size = newSize
  }

  // 返回区间包含 index 的 RangeValue 的值
  getValueAt(index: number): T {
    const result = this.valueTree.search(new Range(index))
    if (result) return result.value
    return this.defaultValue
  }  

  /**
   * 设值方法，
   * 自动与相邻的相同值的合并成更大的 RangeValue，
   * 导致原本的 RangeValue 不连续，则会
   * 自动切分成两个或者三个 RangeValue。
   *
   *         a-------------a
   * |a------------|b------------|c-----------|...
   * 
   * 结果：
   * |a-------------------|b-----|c-----------|...
   * 
   * 
   *         d-------------d
   * |a------------|b------------|c-----------|...
   * 
   * 结果：
   * |a-----|d------------|b-----|c-----------|...
   * 
   */
  setRangeValue(start: number, end: number, value: T) {
    if (!this.size) return
    if (end >= this.size) end = this.size - 1

    // 所有与当前传入区间范围有重叠部分，
    // -1，+1 将接壤的毗邻 RangeValue 也纳入（如果存在的话），
    // 毗邻的 RangeValue 要检查否要合并。
    let prevSiblingEnd = start - 1
    let nextSiblingStart = end + 1
    let rangeValues = this.treeIntersecting(prevSiblingEnd, nextSiblingStart)

    // 如果没有重叠的部分，则作为新的 RangeValue 插入，直接结束
    // 如果有重叠的部分，就要处理合并、拆分
    if (rangeValues.length) {
      let firstRange = rangeValues[0]
      let lastRange = rangeValues[rangeValues.length - 1]

      // end 边界比传入的 start 小，说明是接壤毗邻的更小的 RangeValue
      //
      // 1. 如果毗邻的 RangeValue 的值跟当前带插入的值不一致，
      // 则直接将毗邻的 RangeValue 从列表中移除，
      // 不需要做任何特殊操作，正常的插入操作即可
      //
      // 2. 否则如果毗邻的 RangeValue 的值跟当前待插入的值一致，
      // 则将两个 RangeValue 的 Range 合并（修改 start即可），
      // 然后这个毗邻的 RangeValue 也自然变成重叠的，正常执行后续
      // 的重叠处理逻辑即可（拆分）
      if (firstRange.end < start) {
        if (firstRange.value !== value) {
          rangeValues.shift()
        }
        else {
          start = firstRange.start
        }
      }

      // 接壤毗邻的更大的 RangeValue，处理思路
      // 跟上面处理毗邻的更小的 RangeValue 一样的
      if (lastRange.start > end) {
        if (lastRange.value !== value) {
          rangeValues.pop()
        }
        else {
          end = lastRange.end
        }
      }

      // 结束毗邻 RangeValue 合并逻辑
      // 开始处理相交的 RangeValue 流程
      const length = rangeValues.length
      let index = 0
      while (index < length) {
        const currentRangeValue = rangeValues[index]
        const { value: currentValue, start: currentStart, end: currentEnd } = currentRangeValue

        // 先移除掉该重叠的 RangeValue，然后：
        this.valueTree.delete(currentRangeValue)

        // Case 1. 如果是当前 RangeValue 完整包含在传入的范围内，
        // 则不需要处理，因为整个范围都将被传入的值覆盖。
        if (currentStart >= start && currentEnd <= end) {
          index += 1
          continue
        }

        // Case2. 部分相交，该 RangeValue 的大的一侧在传入的范围内，而小的一侧不在。
        // 需要做切分操作，以重叠的位置作为切分点，比较小的一侧（不重叠的部分）重新插入，
        // 比较大的的那一部分，会被传入的值覆盖掉
        if (currentStart < start) {
          // 如果值不一样，则以相交的位置作为切分点，非重叠部分重新插入，重叠部分用待插入的值覆盖。
          if (currentValue !== value) {
            this._insert(currentStart, start - 1, currentValue)
          }
          else {
            start = currentStart
          }
        }

        // Case3. 部分相交，该 RangeValue 的小的一侧在传入的范围内，而大的一侧不在。
        // 同 Case 2 做切分操作，只是反向。
        if (currentEnd > end) {
          if (currentValue !== value) {
            this._insert(end + 1, currentEnd, currentValue)
          }
          else {
            end = currentEnd
          }
        }

        index += 1
      }
    }

    this._insert(start, end, value)
  }

  setValue(index: number, value: T) {
    this.setRangeValue(index, index, value)
  }

  /**
   * 筛选出与指定区间有重叠的 RangeValue，即：
   * 
   *             1. 相互部分重叠
   * 
   * o----------o              o---------o
   *     >start------------------end<
   * 
   * 
   *            2. 相互完全重叠关系
   * 
   *           o----------------o
   *           >start--------end<
   * 
   * 
   *            3. 包含或被包含关系
   * 
   * o--------------------------------------o
   *   o-------------------------------o
   *      o-------------------------------o
   *      o-----o     o-----o     o----o
   *      >start--------------------end<
   * 
   */
  treeIntersecting(start: number, end: number): RangeValue[] {
    const startRange = new Range(start)
    const endRange = new Range(end)
    return this.valueTree.searchRange(startRange, endRange)
  }

  /**
   * 返回指定范围内所有 RangeValue
   * 范围内有无值的 Range 的话，则使用
   * 携带默认值的 RangeValue 代替
   * 从而确保返回的结果是线性的、每个区间都有值的，如:
   * 
   * start>...<end 范围内有 A、B 两个 RangeValue，所有空洞都用 Default 补足
   * +-----------|-----|-----------|-----|-----------+
   * |  Default  |  A  |  Default  |  B  |  Default  |
   * >start------|-----|-----------|-----|--------end<
   *
   */
  intersecting(start: number, end: number): RangeValue[] {
    const ranges = this.treeIntersecting(start, end)
    if (!ranges.length) {
      if (!this.size) return []
      return [ new RangeValue(start, end, this.defaultValue) ]
    }

    let result = []
    let range
    let index = 0
    let length = ranges.length
    while (index < length) {
      range = ranges[index].clone()
      // 传入的 (start, end) 右侧与某个 RangeValue 重叠，
      // 左侧没有命中，则左侧区域手动塞入一个携带默认
      // 值的 RangeValue
      if (range.start > start) {
        result.push(new RangeValue(start, range.start - 1, this.defaultValue))
      }

      result.push(range)

      // 将 start 的位置右移，
      // 以便下个 range 的比较
      start = range.end + 1
      index += 1
    }

    // 如果最后一个 range，与传入的范围只有左侧重叠，
    // 而右侧没有重叠的地方，则手动塞入一个携带默认值
    // 的 RangeValue
    if (range.end < end) {
      result.push(new RangeValue(range.end + 1, end, this.defaultValue))
    }
    else if (range.end > end) {
      // 否则如果最后一个 range 的范围已经超出需要的范围，则裁剪
      range.end = end
    }

    return result
  }

  values() {
    if (!this.size) return []
    return this.intersecting(0, this.size - 1)
  }

  _insert(start: number, end: number, value: T) {
    if (value !== this.defaultValue) {
      const rangeValue = new RangeValue(start, end, value)
      this.valueTree.insert(rangeValue)
    }
  }
}

export function create<T>(size: number, value: T) {
  return new SparseRangeList(size, value)
}

有了这套存储机制之后，我们就可以更高效地管理列表项的高度，和统计列表高度了。

看代码理解：

import { create as createSparseRangeList } from './SparseRangeList'

// 创建一个默认预估高度为 20 的列表项存储对象
const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)

// 设置第二项为 40px
itemHeightStore.setValue(1, 40)

// 获取第二项的高度
itemHeightStore.getValueAt(1) // 40

// 获取列表项的 top 坐标
const top = (index: number): number => {
  if (index === 0) return 0
  // 0 ～ 上一项的高度累加
  const rangeValues = itemHeightStore.intersecting(0, index - 1)
  const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
    const span = rangeValue.end - rangeValue.start + 1
    return sum + rangeValue.value * span
  }, 0)
  return sumHeight
}

top(1) // 20

// 计算列表总高度：
const listHeight = itemHeightStore
  .values()
  .reduce((acc: number, rangeValue: any) => {
    const span = rangeValue.end - rangeValue.start + 1
    const height = rangeValue.value * span
    return acc + height
  }, 0)

计算可视条目

完成了列表项高度的管理，接下来需要解决的重点，就是计算出哪些条目是可视的。

最简单的实现方式，就是直接遍历我们的结点高度存储列表，逐个去跟视口的坐标区间比较，过滤出落在（或部分落在）视口内部的条目。基于性能考虑，我们当然不能这么简单粗暴。我们可以做以下尝试来提高性能：

一、预估起点条目 + 二分法修正。

通过条目的预估高度或默认高度，算出可能出现在视口的第一条条目。比如，我们视口上沿坐标（即滚动条滚过的距离）为 100px，我们条目预估高度为 20px，那么，我们可以猜测第一个出现在视口中的条目为 100 / 20 + 1，即第 6 条。我们直接计算第 6 条的坐标，检查是否落在视口中，根据结果差距，再进行二分法猜测，直到找到真正的起点条目。

二、预估终点条目 + 二分法修正

在算出起点条目后，在使用视口高度除以预估条目高度，算出视口内部可能显示多少项，将起点序号加上这个数量，就是预估的终点条目序号。使用上述一样的修正逻辑，直到找到正确的视口终点条目。

描述可能比较难以理解，下面给出关键片段：

// 内部方法，计算局部渲染数据切片的起止点
private _calcSliceRange() {
  if (!this.dataView.length) {
    return { sliceFrom: 0, sliceTo: 0 }
  }

  // 数据总量
  const MAX = this.dataView.length

  // 视口上边界
  const viewportTop = (this.$refs.viewport as any).scrollTop || 0
  // 视口下边界
  const viewportBottom = viewportTop + this.viewportHeight
  // 预估条目高度
  const estimatedItemHeight = this.defaultItemHeight

  // 从估算值开始计算起始序号
  let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
  if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
  while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
    const itemTop = this._top(sliceFrom)

    // 条目顶部相对于 viewport 顶部的偏移
    const itemOffset = itemTop - viewportTop

    // 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
    if (itemOffset > 0) {
      // 二分法快速估算下一个尝试位置
      const diff = itemOffset / estimatedItemHeight!
      sliceFrom -= Math.ceil(diff / 2)
      continue
    }

    // 2. 恰好显示该条目的顶部，则该条目为本次视口的首条元素
    if (itemOffset === 0) break

    // 以下都是 itemOffset < 0

    const itemHeight = this._itemHeight(sliceFrom)

    // 3. 该条目在顶部露出了一部分，则该条目为本次视口的首条元素
    if (itemOffset < itemHeight) break

    // 4. 该条目已被滚出去视口，继续测试下一条
    // 二分法快速估算下一个尝试位置
    const diff = -itemOffset / estimatedItemHeight!
    sliceFrom += Math.ceil(diff / 2)
  }

  // 从估算值开始计算结束序号
  let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
  if (sliceTo > MAX) sliceTo = MAX
  while (sliceTo > sliceFrom && sliceTo <= MAX) {
    const itemTop = this._top(sliceTo)
    const itemHeight = this._itemHeight(sliceTo)
    const itemBottom = itemTop + itemHeight

    // 条目底部相对于 viewport 底部的偏移
    const itemOffset = itemBottom - viewportBottom

    // 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
    if (itemOffset < 0) {
      // 二分法快速估算下一个尝试位置
      const diff = -itemOffset / estimatedItemHeight!
      sliceTo += Math.ceil(diff / 2)
      continue
    }

    // 2. 恰好显示该条目的底部，则该条目为视口中最后一项
    if (itemOffset === 0) break

    // 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项
    if (itemOffset < itemHeight) break

    // 该条目还未出场，继续测试上一条
    // 二分法快速估算下一个尝试位置
    const diff = itemOffset / estimatedItemHeight!
    sliceTo -= Math.ceil(diff / 2)
  }
  // slice 的时候，不含 end，所以 + 1
  sliceTo += 1

  return { sliceFrom, sliceTo }
}

以上就是计算可视区域的核心部分。完整的代码，会在后续给出。

DOM 更新

由于我们是使用 Vue 来实现虚拟列表的，所以 DOM 的更新方面，可以省去大量繁琐的细节管理。我们只需要关心列表滚动到某处之后，如何计算出当前视口应该出现哪些条目即可。

尽管如此，考虑到滚动的流畅性，以及 IE11 等浏览器的 DOM 操作性能，我们不得不多做很多事情。

批量 DOM 操作

我们可以在 IE11 的开发者工具面板中看到，滚动过程，频繁地往虚拟列表首尾插入、移除结点，会带来非常严重的性能问题。所以，我们必须控制 DOM 操作的频率。

批量可以部分解决这个问题。

具体的思路是，在滚动回调中，我们计算出可视区域的结点起止序号，不直接应用，而是加上一个额外渲染的数量。比如我们计算出当前应该渲染 20 ~ 30 这些条目，我们可以在前后各加上 10 个额外渲染的条目，即 10 ~ 40，这样就一次性渲染了 30 个结点。在继续滚动时，我们检查新的起止范围，是否还在 10 ～ 40 范围内，如果是，我们就不做新的结点增删操作。

核心实现：

// 刷新局部渲染数据切片范围
private _updateSliceRange(forceUpdate?: boolean) {
  // 上下方额外多渲染的条目波动量
  const COUNT = this._preRenderingCount()

  // 预渲染触发阈值
  const THRESHOLD = this._preRenderingThreshold()    

  // 数据总量
  const MAX = this.dataView.length

  // 计算出准确的切片区间
  const range = this._calcSliceRange()    

  // 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了
  // 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片）
  let fromThreshold = range.sliceFrom - THRESHOLD
  if (fromThreshold < 0) fromThreshold = 0
  let toThreshold = range.sliceTo + THRESHOLD
  if (toThreshold > MAX) toThreshold = MAX

  // 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
  if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
    return
  }

  // 下面是更新切片的情况

  // 在切片区间头部、尾部，追加预渲染的条目
  let { sliceFrom, sliceTo } = range
  sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0
  sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT

  this.sliceFrom = sliceFrom
  this.sliceTo = sliceTo
  if (forceUpdate) this._doSlice()
}

使用了这种批量操作之后，可以看到，正常的鼠标滚动下，IE 也能比较顺畅地滚动了。

事件

由于虚拟列表的 DOM 需要不停地生成和销毁，因此，直接在列表项目上绑定事件是非常低效的。所以，使用事件代理就成了很不错的方案，将事件注册在组件根结点上，再根据 event.target 来区分是由哪个列表项冒泡出来的事件，即可高效处理。

组件实现

import { Component, Vue, Prop, Watch } from 'vue-property-decorator'
import { createSparseRangeList } from './SparseRangeList'

// 列表项数据包裹，data 字段存放原始数据
// 组件所有操作不应该改变 data 的内容，而是修改该包裹对象的属性
class ItemWrapper {
  // 原始数据
  data: any

  // 数据唯一 key
  key: any

  // 条目高度
  // 1. 正数代表已经计算出来的高度
  // 2. 0 代表未计算的高度，不显示
  // 3. 负数代表需要隐藏的高度，绝对值为已经计算出来的高度，方便取消隐藏
  height: number

  // 记录是否已经根据实际 DOM 计算过高度
  realHeight: boolean

  // 条目在当前过滤视图中的序号
  viewIndex: number

  constructor(data: any, key: any, height: number) {
    this.data = data

    // 数据的唯一id，是初始化数据时候的序号
    // 每次传入的 data 改变，都会重新生成
    this.key = key

    // 条目的高度缓存
    // 1. 用于重建高度存储时快速恢复
    // 2. 用于快速通过数据取高度
    this.height = height >> 0

    this.realHeight = false

    // 每次生成 dataView 都刷新
    this.viewIndex = -1
  }
}

@Component({ name: 'VList' })
export default class VList extends Vue {
  [key: string]: any

  // 高度存储 不响应式
  private itemHeightStore: any

  // 组件宽度，不设置则为容器的 100%
  @Prop({ type: Number })
  private width?: number

  // 组件高度，不设置则为容器的 100%
  @Prop({ type: Number })
  private height?: number

  // 传入高度值，固定条目高度
  @Prop({ type: Number })
  private fixedItemHeight?: number

  // 预估元素高度，
  // 在高度不确定的列表中，未计算出高度时使用，
  // 该值与元素平均高度越相近，则越高效（修正时估算次数越少）
  @Prop({ type: Number, default: 30 })
  private estimatedItemHeight!: number

  // 数据列表
  @Prop({ type: Array, default: () => ([]) })
  private data!: any[]

  // 计算条目高度的方法
  @Prop({
    type: Function,
    default(node: Node, wrappedData: ItemWrapper) {
      return (node as HTMLElement).clientHeight
    }
  })
  private itemHeightMethod!: (node: Node, wrappedItem: ItemWrapper) => number

  // 数据过滤方法（可以用于外部实现搜索框过滤）
  @Prop({ type: Function })
  private filterMethod?: (data: any) => boolean

  // 数据排序方法（可以用于外部实现数据自定义过滤）
  @Prop({ type: Function })
  private sortMethod?: (a: any, b: any) => number

  // 包裹后的数据列表（必须 freeze，否则大列表性能撑不住）
  private wrappedData: ReadonlyArray<ItemWrapper> = Object.freeze(this._wrapData(this.data))

  // 真实渲染上屏的数据列表切片
  private dataSlice: ReadonlyArray<ItemWrapper> = []

  // viewport 宽度
  private viewportWidth = this.width || 0

  // viewport 高度
  private viewportHeight = this.height || 0

  // 当前 viewport 中第一条数据的序号
  private sliceFrom = 0

  // 当前 viewport 中最后一条数据的序号
  private sliceTo = 0

  // 列表高度
  private listHeight = 0

  // 检查是否固定高度模式
  private get isFixedHeight() {
    return this.fixedItemHeight! >= 0
  }

  // 获取默认条目高度
  private get defaultItemHeight() {
    return this.isFixedHeight ? this.fixedItemHeight! : this.estimatedItemHeight
  }

  // 当前筛选条件下的数据列表
  // 依赖：wrappedData, filterMethod, sortMethod
  private get dataView() {
    const { wrappedData, filterMethod, sortMethod } = this
    let data = []
    if (typeof filterMethod === 'function') {
      const len = wrappedData.length
      for (let index = 0; index < len; index += 1) {
        const item = wrappedData[index]
        if (filterMethod(item.data)) {
          data.push(item)
        }
      }
    } else {
      data = wrappedData.map(i => i)
    }
    if (typeof sortMethod === 'function') {
      data.sort((a, b) => {
        return sortMethod(a, b)
      })
    }

    // 重新记录数据在视图中的位置，用于隐藏部分条目时，可以精确计算高度、坐标
    const size = data.length
    for (let index = 0; index < size; index += 1) {
      const wrappedItem = data[index]
      wrappedItem.viewIndex = index
    }

    return Object.freeze(data)
  }

  // 原始列表数据变化，重新包裹数据
  @Watch('data')
  private onDataChange(data: any[]) {
    this.wrappedData = Object.freeze(this._wrapData(data))
  }

  // 当前过滤、排序视图变化，重新布局
  @Watch('dataView')
  private onDataViewChange(wrappedItems: ItemWrapper[]) {
    // 重建高度存储
    const estimatedItemHeight = this.defaultItemHeight
    this.itemHeightStore = createSparseRangeList(wrappedItems.length, estimatedItemHeight)
    // 从缓存中快速恢复已计算出高度的条目的高度
    wrappedItems.forEach((wrappedItem, index) => {
      // 小于零的需要隐藏，所以高度为 0
      this.itemHeightStore.setValue(index,
        wrappedItem.height > 0 ? wrappedItem.height : 0)
    })

    // 刷新列表高度
    this.updateListHeight()

    // 重置滚动位置
    // TODO, 锚定元素
    const { viewport } = this.$refs as any
    if (viewport) viewport.scrollTop = 0

    // 重新切片当前 viewport 需要的数据
    this._updateSliceRange(true)

    this.$emit('data-view-change', this.dataSlice.map((wrappedItem) => wrappedItem.data))
  }

  private created() {
    const estimatedItemHeight = this.defaultItemHeight
    this.itemHeightStore = createSparseRangeList(this.dataView.length, estimatedItemHeight)
    this.layoutObserver = new MutationObserver(this.redraw.bind(this))
    this.childObserver = new MutationObserver((mutations: MutationRecord[]) => {
      this._updateHeightWhenItemInserted(mutations)
    })

    this.$watch(((vm: any) => `${vm.sliceFrom},${vm.sliceTo}`) as any, this._doSlice)
  }

  private mounted() {
    this.redraw()
    this.layoutObserver.observe(this.$el, { attributes: true })

    // 非固定高度场景，监听子元素插入，提取高度
    if (!this.isFixedHeight) {
      this.childObserver.observe(this.$refs.content, { childList: true })
    }
  }

  private beforeDestory() {
    this.layoutObserver.disconnect()
    if (!this.isFixedHeight) {
      this.childObserver.disconnect()
    }
    this.itemHeightStore = null
  }

  // DOM 结构比较简单，无需 template，直接使用渲染函数输出 VDOM
  private render(createElement: any) {
    return createElement(
      'div', // 组件容器，与外部布局
      {
        class: 'VList',
        style: {
          'box-sizing': 'border-box',
          display: 'inline-block',
          margin: '0',
          padding: '0',
          width: this.width ? this.width + 'px' : '100%',
          height: this.height ? this.height + 'px' : '100%',
        }
      },
      [
        createElement(
          'div', // 滚动区域的可见范围
          {
            ref: 'viewport',
            class: 'VList_viewport',
            style:
              'box-sizing:border-box;position:relative;overflow:hidden;width:100%;height:100%;margin:0;padding:0;overflow:auto;overflow-scrolling:touch;',
            on: { scroll: this._onScroll }
          },
          [
            createElement(
              'div', // 内容容器，内容真实高度由此容器体现
              {
                class: 'VList_scollable',
                ref: 'content',
                style: {
                  'box-sizing': 'border-box',
                  position: 'relative',
                  margin: '0',
                  padding: '0',
                  height: this.listHeight + 'px'
                }
              },
              // 列表项
              this.dataSlice.map((wrappedItem) => {
                return createElement(
                  'div',
                  {
                    key: wrappedItem.key,
                    class: `VList_item VList_item-${wrappedItem.key % 2 === 0 ? 'even' : 'odd'}`,
                    attrs: {
                      'data-key': wrappedItem.key
                    },
                    style: {
                      'box-sizing': 'border-box',
                      'z-index': '1',
                      position: 'absolute',
                      right: '0',
                      bottom: 'auto',
                      left: '0',
                      margin: '0',
                      padding: '0',
                      cursor: 'default',
                      // 注：使用 transfrom 有黑屏 bug
                      // transform: `translate(0, ${top})`
                      // transform: `translate3d(0, ${top}, 0)`
                      top: this._top(wrappedItem.viewIndex) + 'px'
                    }
                  },

                  // 将原始数据，key 注入到 slot 里，
                  // 以便自定义条目内容使用
                  this.$scopedSlots.default!({
                    item: wrappedItem.data,
                    listKey: wrappedItem.key
                  })
                )
              })
            )
          ]
        )
      ]
    )
  }

  // 重绘界面，确保列表渲染正确
  public redraw() {
    const viewport = this.$refs.viewport as HTMLElement
    const { clientWidth, clientHeight } = viewport
    this.viewportWidth = clientWidth
    this.viewportHeight = clientHeight
    this.updateListHeight()
    this._updateSliceRange(true)
  }

  // 刷新列表总高度
  public updateListHeight() {
    const { itemHeightStore } = this
    const rangeValues = itemHeightStore.values()
    if (!rangeValues.length) {
      this.listHeight = 0
      return
    }
    const listHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
      const span = rangeValue.end - rangeValue.start + 1
      const height = rangeValue.value * span
      return sum + height
    }, 0)
    this.listHeight = listHeight
  }

  // Dom 插入时候，计算高度，然后
  // 批量刷新高度，避免频繁调整列表高度带来性能问题
  public batchUpdateHeight(records: Array<{ wrappedItem: ItemWrapper, height: number }>) {
    records.forEach(({ wrappedItem, height }) => {
      this._updateHeight(wrappedItem, height, true)
    })
    this.updateListHeight()
    this._updateSliceRange()
  }

  // 通过数据 key，设置对应条目的高度
  public updateHeightByKey(key: any, height: number) {
    const wrappedItem = this.wrappedData[key]
    if (!wrappedItem) return
    this._updateHeight(wrappedItem, height)
    this.updateListHeight()
    this._updateSliceRange()
  }

  // 通过数据 key，设置对应条目的显示状态
  public showByKey(key: any) {
    const wrappedItem = this.wrappedData[key]
    if (!wrappedItem) return
    if (wrappedItem.height <= 0) {
      const height = -wrappedItem.height || this.defaultItemHeight
      this._updateHeight(wrappedItem, height!)
      this.updateListHeight()
      this._updateSliceRange()
      // 强制重绘
      this._doSlice()
    }
  }

  // 通过数据 key，设置对应条目的显示状态
  public hideByKey(key: any) {
    const wrappedItem = this.wrappedData[key]
    if (!wrappedItem) return
    if (wrappedItem.height > 0) {
      const height = -wrappedItem.height
      wrappedItem.height = height
      this._updateHeight(wrappedItem, height)
      this.updateListHeight()
      // 强制重绘
      this._updateSliceRange(true)
    }
  }

  // 通过数据 key 列表，设置对应条目的显示状态
  public showByKeys(keys: any[]) {
    const wrappedItems = keys.map((key) => this.wrappedData[key])
      .filter((wrappedItem) => wrappedItem && wrappedItem.height <= 0)
    wrappedItems.forEach((wrappedItem) => {
      const height = (-wrappedItem.height || this.defaultItemHeight)!
      this._updateHeight(wrappedItem, height)
    })
    this.updateListHeight()
    // 强制重绘
    this._updateSliceRange(true)
  }

  // 通过数据 key 列表，设置对应条目的显示状态
  public hideByKeys(keys: any[]) {
    const wrappedItems = keys.map((key) => this.wrappedData[key])
      .filter(wrappedItem => wrappedItem && wrappedItem.height > 0)
    wrappedItems.forEach((wrappedItem) => {
      // 设置为负数，表示隐藏
      const height = -wrappedItem.height
      wrappedItem.height = height
      this._updateHeight(wrappedItem, height)
    })
    this.updateListHeight()
    // 强制重绘
    this._updateSliceRange(true)
  }

  // 内部方法，计算局部渲染数据切片的起止点
  private _calcSliceRange() {
    if (!this.dataView.length) {
      return { sliceFrom: 0, sliceTo: 0 }
    }

    // 数据总量
    const MAX = this.dataView.length

    // 视口上边界
    const viewportTop = (this.$refs.viewport as any).scrollTop || 0
    // 视口下边界
    const viewportBottom = viewportTop + this.viewportHeight
    // 预估条目高度
    const estimatedItemHeight = this.defaultItemHeight

    // 从估算值开始计算起始序号
    let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
    if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
    while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
      const itemTop = this._top(sliceFrom)

      // 条目顶部相对于 viewport 顶部的偏移
      const itemOffset = itemTop - viewportTop

      // 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
      if (itemOffset > 0) {
        // 二分法快速估算下一个尝试位置
        const diff = itemOffset / estimatedItemHeight!
        sliceFrom -= Math.ceil(diff / 2)
        continue
      }

      // 2. 恰好显示该条目的顶部，则该条目为本次视口的首条元素
      if (itemOffset === 0) break

      // 以下都是 itemOffset < 0

      const itemHeight = this._itemHeight(sliceFrom)

      // 3. 该条目在顶部露出了一部分，则该条目为本次视口的首条元素
      if (itemOffset < itemHeight) break

      // 4. 该条目已被滚出去视口，继续测试下一条
      // 二分法快速估算下一个尝试位置
      const diff = -itemOffset / estimatedItemHeight!
      sliceFrom += Math.ceil(diff / 2)
    }

    // 从估算值开始计算结束序号
    let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
    if (sliceTo > MAX) sliceTo = MAX
    while (sliceTo > sliceFrom && sliceTo <= MAX) {
      const itemTop = this._top(sliceTo)
      const itemHeight = this._itemHeight(sliceTo)
      const itemBottom = itemTop + itemHeight

      // 条目底部相对于 viewport 底部的偏移
      const itemOffset = itemBottom - viewportBottom

      // 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
      if (itemOffset < 0) {
        // 二分法快速估算下一个尝试位置
        const diff = -itemOffset / estimatedItemHeight!
        sliceTo += Math.ceil(diff / 2)
        continue
      }

      // 2. 恰好显示该条目的底部，则该条目为视口中最后一项
      if (itemOffset === 0) break

      // 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项
      if (itemOffset < itemHeight) break

      // 该条目还未出场，继续测试上一条
      // 二分法快速估算下一个尝试位置
      const diff = itemOffset / estimatedItemHeight!
      sliceTo -= Math.ceil(diff / 2)
    }
    // slice 的时候，不含 end，所以 + 1
    sliceTo += 1

    return { sliceFrom, sliceTo }
  }

  // 上下两端预先批量渲染的项目波动量
  // 原理是，每次插入删除都是一个小批量动作，
  // 而不是每次只插入一条、销毁一条
  // 计算出的局部渲染数据范围，跟上一次计算出来的结果，差距
  // 在这个波动量范围内，则不重新切片渲染，用于
  // 防止 IE 11 频繁插入内容导致性能压力
  private _preRenderingCount() {
    // 默认预渲染 2 屏
    return Math.ceil(this.viewportHeight / this.defaultItemHeight!) * 2
  }
  
  // 滚动到上下方剩下多少个条目时，加载下一批
  // 缓解 Macbook & iOS 触摸滚动时的白屏
  private _preRenderingThreshold() {
    // 默认触达预渲染的一半数量时，加载下一批切片
    return Math.floor(this._preRenderingCount() / 2)
  }

  // 刷新局部渲染数据切片范围
  private _updateSliceRange(forceUpdate?: boolean) {
    // 上下方额外多渲染的条目波动量
    const COUNT = this._preRenderingCount()

    // 预渲染触发阈值
    const THRESHOLD = this._preRenderingThreshold()    

    // 数据总量
    const MAX = this.dataView.length

    // 计算出准确的切片区间
    const range = this._calcSliceRange()    

    // 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了
    // 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片）
    let fromThreshold = range.sliceFrom - THRESHOLD
    if (fromThreshold < 0) fromThreshold = 0
    let toThreshold = range.sliceTo + THRESHOLD
    if (toThreshold > MAX) toThreshold = MAX

    // 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
    if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
      return
    }

    // 更新切片的情况

    // 在切片区间头部、尾部，追加预渲染的条目
    let { sliceFrom, sliceTo } = range
    sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0
    sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT

    this.sliceFrom = sliceFrom
    this.sliceTo = sliceTo
    if (forceUpdate) this._doSlice()
  }

  // 当前需要渲染的数据切片
  private _doSlice() {
    const { dataView, sliceFrom, sliceTo } = this
    const slice = dataView.slice(sliceFrom, sliceTo)
      .filter((wrappedItem) => wrappedItem.height > 0)
    this.dataSlice = Object.freeze(slice)
    this.$emit('slice', slice.map((wrappedItem) => wrappedItem.data))
  }

  // `index` 数据在 dataView 中的 index
  private _itemHeight(index: number): number {
    return this.itemHeightStore.getValueAt(index)
  }

  // `index` 数据在 dataView 中的 index
  private _top(index: number): number {
    if (index === 0) return 0
    // 0 ～ 上一项的高度累加
    const rangeValues = this.itemHeightStore.intersecting(0, index - 1)
    const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
      const span = rangeValue.end - rangeValue.start + 1
      return sum + rangeValue.value * span
    }, 0)
    return sumHeight
  }

  // 包裹原始数据列表
  private _wrapData(list: any[]): ItemWrapper[] {
    return list.map((item, index) => new ItemWrapper(item, index, this.defaultItemHeight!))
  }

  // 通过 DOM Node 获取对应的数据
  private _getDataByNode(node: Node): ItemWrapper {
    return this.wrappedData[(node as any).dataset.key]
  }

  // 刷新列表项高度
  private _updateHeight(wrappedItem: ItemWrapper, height: number, isRealHeight?: boolean) {
    height = height >> 0
    // 更新结点高度缓存
    wrappedItem.height = height

    if (isRealHeight) {
      wrappedItem.realHeight = true
    }

    // 如果 wrappedItem 为当前过滤下的项目，
    // 则同时刷新高度存储 store。
    const index = this.dataView.indexOf(wrappedItem)
    if (index !== -1) {
      // 小于等于零表示折叠不显示，计算高度为零
      // 负值存在 wrappedItem 中，用于反折叠时恢复
      this.itemHeightStore.setValue(index, height > 0 ? height : 0)
    }
  }

  // 节点插入时，检查是否首次插入，如果是，计算高度并更新对应的 ItemWrapper
  private _updateHeightWhenItemInserted(mutations: MutationRecord[]) {
    const addedNodes: Node[] = mutations
      .map((mutation: MutationRecord) => mutation.addedNodes)
      .reduce((result: any, items: NodeList) => {
        result.push(...items)
        return result
      }, [])

    const batch: Array<{ wrappedItem: ItemWrapper, height: number }> = []
    addedNodes.forEach((node: Node) => {
      const wrappedItem = this._getDataByNode(node)

      // 如果 wrappedItem 中已经存储了计算过的高度，
      // 则直接返回，不访问 clientHeight
      // 以避免性能开销（IE 11 中访问 clientHeight 性能非常差）
      if (wrappedItem.realHeight) {
        return
      }

      const height = this.itemHeightMethod(node, wrappedItem) >> 0
      if (wrappedItem.height !== height) {
        batch.push({ wrappedItem, height })
      } else {
        // 计算出来的高度跟默认值一致，
        // 则无需更新，但是设置已经计算状态
        // 以便下次可以直接使用缓存
        wrappedItem.realHeight = true
      }
    })

    if (batch.length) {
      this.batchUpdateHeight(batch)
    }
  }

  // 滚动事件处理器
  private _onScroll() {
    this._updateSliceRange()
  }
}