浅说虚拟列表的实现原理

jiezi

6 年前

在列表数据的展示优化一文中，提到了对于列表形态的数据展示的按需渲染。这种方式是指根据容器元素的高度以及列表项元素的高度来显示长列表数据中的某一个部分，而不是去完整地渲染长列表，以提高无限滚动的性能。而按需显示方案的实现就是本文标题中说的虚拟列表。
虚拟列表的实现有多种方案，本文以 react-virtual-list 组件为基础进行分析。原文链接：https://github.com/dwqs/blog/…

什么是虚拟列表？
在正文之前，先对虚拟列表做个简单的定义。
根据上文，虚拟列表是按需显示思路的一种实现，即虚拟列表是一种根据滚动容器元素的可视区域来渲染长列表数据中某一个部分数据的技术。
简而言之，虚拟列表指的就是「可视区域渲染」的列表。有三个概念需要了解一下：

滚动容器元素：一般情况下，滚动容器元素是 window 对象。然而，我们可以通过布局的方式，在某个页面中任意指定一个或者多个滚动容器元素。只要某个元素能在内部产生横向或者纵向的滚动，那这个元素就是滚动容器元素考虑每个列表项只是渲染一些纯文本。在本文中，只讨论元素的纵向滚动。

可滚动区域：滚动容器元素的内部内容区域。假设有 100 条数据，每个列表项的高度是 50，那么可滚动的区域的高度就是 100 * 50。可滚动区域当前的具体高度值一般可以通过 (滚动容器) 元素的 scrollHeight 属性获取。用户可以通过滚动来改变列表在可视区域的显示部分。

可视区域：滚动容器元素的视觉可见区域。如果容器元素是 window 对象，可视区域就是浏览器的视口大小(即视觉视口)；如果容器元素是某个 div 元素，其高度是 300，右侧有纵向滚动条可以滚动，那么视觉可见的区域就是可视区域。

实现虚拟列表就是在处理用户滚动时，要改变列表在可视区域的渲染部分，其具体步骤如下：

计算当前可见区域起始数据的 startIndex
计算当前可见区域结束数据的 endIndex
计算当前可见区域的数据，并渲染到页面中
计算 startIndex 对应的数据在整个列表中的偏移位置 startOffset，并设置到列表上
计算 endIndex 对应的数据相对于可滚动区域最底部的偏移位置 endOffset，并设置到列表上

建议参考下图理解一下上面的步骤：

元素 L 代指当前列表中的最后一个元素
从上图可以看出，startOffset 和 endOffset 会撑开容器元素的内容高度，让其可持续的滚动；此外，还能保持滚动条处于一个正确的位置。
为什么需要虚拟列表？
虚拟列表是对长列表的一种优化方案。在前端开发中，会碰到一些不能使用分页方式来加载列表数据的业务形态，我们称这种列表叫做长列表。比如，在一些外汇交易系统中，前端会准实时的展示用户的持仓情况(收益、亏损、手数等)，此时对于用户的持仓列表一般是不能分页的。
在本篇文章中，我们把长列表定义成数据长度大于 999，并且不能使用分页的形式来展示的列表。
如果对长列表不作优化，完整地渲染一个长列表，到底需要多长时间呢？接下来会写一个简单的 demo 来测试以下。
本文 demo 的测试环境：Macbook Pro(Core i7 2.2G, 16G), Chrome 69，React 16.4.1
在 demo 中，我们先测一下浏览器渲染 10000 个简单的节点需要多长时间：
import React from ‘react’

const count = 10000

function createMarkup (doms) {
return doms.length ? {__html: doms.join(‘ ‘) } : {__html: ”}
}

export default class DOM extends React.Component {
constructor (props) {
super(props)
this.state = {
simpleDOMs: []
}

this.onCreateSimpleDOMs = this.onCreateSimpleDOMs.bind(this)
}

onCreateSimpleDOMs () {
const array = []

for (var i = 0; i < count; i++) {
array.push(‘<div>’ + i + ‘</div>’)
}

this.setState({
simpleDOMs: array
})
}

render () {
return (
<div style={{marginLeft: ’10px’}}>
<h3>Creat large of DOMs：</h3>
<button onClick={this.onCreateSimpleDOMs}>Create Simple DOMs</button>
<div dangerouslySetInnerHTML={createMarkup(this.state.simpleDOMs)} />
</div>
)
}
}
当点击 Button 时，会调用 onCreateSimpleDOMs 创建 10000 个简单节点。从 Chrome 的 Performance 标签页看到的数据如下：

从上图可以看到，从 Event Click 到 Paint，总共用了大约 693ms，渲染时的主要时间消耗情况如下：

Recalculate Style：40.80ms
Layout：518.55ms
Update Layer Tree：11.84ms

在 Recalculate Style 和 Layout 阶段，ReactDOM 调用了 setInnerHTML 方法，其内部主要通过 innerHTML 方法，将创建好的 html 片段添加到对应节点
然后，我们创建 10000 个稍微复杂点的节点。修改组件如下：
import React from ‘react’

function createMarkup (doms) {
return doms.length ? {__html: doms.join(‘ ‘) } : {__html: ”}
}

export default class DOM extends React.Component {
constructor (props) {
super(props)
this.state = {
complexDOMs: []
}

this.onCreateComplexDOMs = this.onCreateComplexDOMs.bind(this)
}

onCreateComplexDOMs () {
const array = []
for (var i = 0; i < 5000; i++) {
array.push(`
<div class=’list-item’>
<p>#${i} eligendi voluptatem quisquam</p>
<p>Modi autem fugiat maiores. Doloremque est sed quis qui nobis. Accusamus dolorem aspernatur sed rem.</p>
</div>
`)
}

this.setState({
complexDOMs: array
})
}

render () {
return (
<div style={{marginLeft: ’10px’}}>
<h3>Creat large of DOMs：</h3>
<button onClick={this.onCreateComplexDOMs}>Create Complex DOMs</button>
<div dangerouslySetInnerHTML={createMarkup(this.state.complexDOMs)} />
</div>
)
}
}
当点击 Button 时，会调用 onCreateComplexDOMs。从 Chrome 的 Performance 标签页看到的数据如下：

从上图可以看到，从 Event Click 到 Paint，总共用了大约 964.2ms，渲染时的主要时间消耗情况如下：

Recalculate Style：117.07ms
Layout：538.00ms
Update Layer Tree：31.15ms

对于上述测试各进行 5 次，然后取各指标的平均值，统计结果如下：

–
Recalculate Style
Layout
Update Layer Tree
Total

渲染简单节点
199.66ms
523.72ms
12.572ms
735.952ms

渲染复杂节点
114.684ms
806.05ms
31.328ms
952.512ms

Total = Recalculate Style + Layout + Update Layer Tree
demo 的测试代码：test code

从上面的测试结果中可以看到，渲染 10000 个节点就需要 700ms+，实际业务中的列表每个节点都需要 20 个左右的节点，布局也会复杂很多，在 Recalculate Style 和 Layout 阶段也会耗费更长的时间。那么，700ms 也仅能渲染 300 ~ 500 个左右的列表项，所以完整的长列表渲染基本上很难达到业务上的要求的。而非完整的长列表渲染一般有两种方式：按需渲染和延迟渲染(即懒渲染)。常见的无限滚动便是延迟渲染的一种实现，而虚拟列表则是按需渲染的一种实现。
延迟渲染不在本文讨论范围。接下来，本文会简单介绍虚拟列表的一种实现方案。
实现
本章节将会创建一个 VirtualizedList 组件，并结合代码，慢慢梳理虚拟列表的实现。
为了简化，我们设定 window 为滚动容器元素，给 html 和 body 元素均添加样式规则 height: 100%，设定可视区域为浏览器的窗口大小。VirtualizedList 在 DOM 元素的布局上将参考 Twitter 的移动端：
class VirtualizedList extends Component {
constructor (props) {
super(props)

this.state = {
startOffset: 0,
endOffset: 0,
visibleData: []
}

this.data = new Array(1000).fill(true)
this.startIndex = 0
this.endIndex = 0
this.scrollTop = 0
}

render () {
const {startOffset, endOffset} = this.state

return (
<div className=’wrapper’>
<div style={{paddingTop: `${startOffset}px`, paddingBottom: `${endOffset}px` }}>
{
// render list
}
</div>
</div>
)
}
}
在虚拟列表上的实现上，也分为两种情形：列表项是固定高度的和列表项是动态高度的。
列表项是固定高度的
既然列表项是固定高度的，那约定没个列表项的高度为 60，列表数据的长度为 1000。
首先，我们根据可视区域的高度估算可视区域能渲染的元素个数：
const height = 60
const bufferSize = 5
// …

this.visibleCount = Math.ceil(window.clientHeight / height)
然后，计算 startIndex 和 endIndex，并先初始化初次需要渲染的数据：
// …

updateVisibleData (scrollTop) {
const visibleData = this.data.slice(this.startIndex, this.endIndex)
const endOffset = (this.data.length – this.endIndex) * height

this.setState({
startOffset: 0,
endOffset,
visibleData
})
}

componentDidMount () {
// 计算可渲染的元素个数
this.visibleCount = Math.ceil(window.innerHeight / height) + bufferSize
this.endIndex = this.startIndex + this.visibleCount
this.updateVisibleData()
}
如上文所说，endOffset 是计算 endIndex 对应的数据相对于可滚动区域底部的偏移位置。在本 demo 中，可滚动区域的高度就是 1000 60，因而 endIndex 对应的数据相距底部的偏移就是 (1000 – endIndex) 60。
由于是初始化初次需要渲染的数据，因而 startOffset 的初始值是 0。
根据上述代码，可以得知，要计算可见区域需要渲染的数据，只要计算出 startIndex 就行，因为 visibleCount 是一个定值，bufferSize 是一个缓冲值，用来增加一定的缓存区域，让正常滑动速度的时候不会显得那么突兀。而 endIndex 的值就等于 startIndex 加上 visibleCount；同时，当用户滚动改变可见区域的数据时，还需要计算 startOffset 的值，以保证新的数据会出现在用户浏览器的视口中：

如果不计算 startOffset 的值，那本应该渲染在可视区域内的元素会渲染到可视区域之外。从上图可以看到，startOffset 的值就是元素 8 的上边框 (可视区域内最上面一个元素) 到元素 1 的上边框的偏移量。元素 8 称为锚点元素，即可视区域内的第一个元素。因而，我们需要定义一个变量来缓存锚点元素的一些位置信息，同时也要缓存已渲染的元素的位置信息：
// …
// 缓存已渲染元素的位置信息
this.cache = []
// 缓存锚点元素的位置信息
this.anchorItem = {
index: 0, // 锚点元素的索引值
top: 0, // 锚点元素的顶部距离第一个元素的顶部的偏移量(即 startOffset)
bottom: 0 // 锚点元素的底部距离第一个元素的顶部的偏移量
}
// …

cachePosition (node, index) {
const rect = node.getBoundingClientRect()
const top = rect.top + window.pageYOffset

this.cache.push({
index,
top,
bottom: top + height
})
}

// …
方法 cachePosition 会在每个列表项组件渲染完后 (componentDidMount) 进行调用，node 是对应的列表项节点元素，index 是节点的索引值：
// Item.jsx

// …
componentDidMount () {
this.props.cachePosition(this.node, this.props.index)
}

render () {
/* eslint-disable-next-line */
const {index} = this.props

return (
<div className=’list-item’ ref={node => { this.node = node}}>
<p>#${index} eligendi voluptatem quisquam</p>
<p>Modi autem fugiat maiores. Doloremque est sed quis qui nobis. Accusamus dolorem aspernatur sed rem.</p>
</div>
)
}
// …
缓存了锚点元素和已渲染元素的位置信息之后，接下来就可以处理用户的滚动行为了。以用户向下滚动 (scrollTop 值增大的方向) 为例：
// …
// 计算 startIndex 和 endIndex
updateBoundaryIndex (scrollTop) {
scrollTop = scrollTop || 0
// 用户正常滚动下，根据 scrollTop 找到新的锚点元素位置
const anchorItem = this.cache.find(item => item.bottom >= scrollTop)

this.anchorItem = {
…anchorItem
}

this.startIndex = this.anchorItem.index
this.endIndex = this.startIndex + this.visibleCount
}

// 滚动事件处理函数
handleScroll (e) {
if (!this.doc) {
// 兼容 iOS Safari/Webview
this.doc = window.document.body.scrollTop ? window.document.body : window.document.documentElement
}

const scrollTop = this.doc.scrollTop
if (scrollTop > this.scrollTop) {
if (scrollTop > this.anchorItem.bottom) {
this.updateBoundaryIndex(scrollTop)
this.updateVisibleData()
}
} else if (scrollTop < this.scrollTop) {
// 向上滚动(`scrollTop` 值减小的方向)
}

this.scrollTop = scrollTop
}
// …
在滚动事件处理函数中，会去更新 startIndex、endIndex 以及新的锚点元素的位置信息(即更新 startOffset)，然后就可以动态的去更新可视区域的渲染数据了：

完整的代码在可以戳：固定高度的虚拟列表实现

列表项是动态高度的
这种情形下，实现的思路和列表项固高大同小异。而小异之处就在于缓存列表项的位置信息时，怎么拿到列表项的精确高度？首先要更改 cachePosition 的部分逻辑：
// …
cachePosition (node, index) {
const rect = node.getBoundingClientRect()
const top = rect.top + window.pageYOffset

this.cache.push({
index,
top,
bottom: top + rect.height // 将 height 更为 rect.height
})
}
// …
由于列表项的高度不固定，那要怎么计算 visibleCount 呢？我们先考虑每个列表项只是渲染一些纯文本。在实际项目中，有的列表项可能只有一行文本，有的列表项可能有多行文本，此时，我们要基于项目的实际情况，给列表项一个预估的高度：estimatedItemHeight。
比如，有一个长列表要渲染用户的文章摘要，并规定摘要显示不超过三行，那么我们取列表的前 10 个列表项的高度平均值作为预估高度。当然，为了预估高度更精确，我们是可以扩大取样样本的。
既然有了预估高度，那么将原先代码中的 height 替换成 estimatedItemHeight，就可以计算出 visibleCount 了：
// …
const estimatedItemHeight = 80

// …

// 计算可渲染的元素个数
this.visibleCount = Math.ceil(window.innerHeight / estimatedItemHeight) + bufferSize

// …
我们通过 faker.js 来创建一些随机数据，并赋值给 data：
// …
function fakerData () {
const a = []
for (let i = 0; i < 1000; i++) {
a.push({
id: i,
words: faker.lorem.words(),
paragraphs: faker.lorem.sentences()
})
}

return a
}
// …

this.data = fakerData()

// …
修改一下列表项的 render 逻辑，其它不变：
// Item.jsx

// …

render () {
/* eslint-disable-next-line */
const {index, item} = this.props

return (
<div className=’list-item’ style={{height: ‘auto’}} ref={node => { this.node = node}}>
<p>#${index} {item.words}</p>
<p>{item.paragraphs}</p>
</div>
)
}
// …
此时，列表项的高度已经是动态的了，根据渲染的实际情况，我们给的预估高度是 80：

完整的代码在可以戳：动态高度的虚拟列表实现

那如果列表项渲染的不是纯文本呢？比如渲染的是图文，那在 Item 组件的 componentDidMount 去调用 cachePosition 方法时，能拿到对应节点的正确高度吗？在渲染图文的情况下，因为图片会发起网络请求，此时并不能保证在列表项组件挂载 (执行 componentDidMount) 的时候图片渲染好了，那此时对应节点的高度就是不准确的，因而在用户滚动改变可见区域渲染的数据时，就可能出现元素相互重叠的情况：

在这种情况下，如果我们能监听 Item 组件节点的大小变化就能获取其正确的高度了。ResizeObserver 或许就可以满足我们的需求，其提供了监听 DOM 元素大小变化的能力，但在撰写本文时，仅 Chrome 67 及以上版本支持，其它主流浏览器均为提供支持。以下是我搜集的一些资料，供你参考(自备梯子)：

ResizeObserver: It’s Like document.onresize for Elements
ResizeObserver
caniuse#resizeobserver

总结
在本文中，首先对虚拟列表进行了简单的定义，然后从长列表的角度分析了为什么需要虚拟列表，最后就列表项固高和不固高两个场景下以一个简单的 demo 详细讲述了虚拟列表的实现思路。
在列表项是动态高度的场景下，分析了渲染纯文本和图文混合的场景。前者给出了一个具体的 demo，针对后者对于怎么监听元素大小的变化提供了参考的 ResizeObserver 方案。基于 ResizeObserver 的方案呢，我也实现了一个支持渲染图文混合 (当然也支持纯文本) 的虚拟列表组件 react-virtual-list，供你参考。
当然，这并不是唯一一种实现虚拟列表的方案。在组件 react-virtual-list 的实现过程中，也阅读了不同虚拟列表组件的源码，如: react-tiny-virtual-list、react-window、react-virtualized 等，后续的系列文章我会从源码的角度逐一分析。
原文：https://github.com/dwqs/blog/…
参考

Complexities of an Infinite Scroller
Infinite List and React
聊聊前端开发中的长列表
再谈前端虚拟列表的实现