阶梯访问表
最后更新于:2022-04-02 04:16:20
[TOC]
## 概述
![](https://files.catbox.moe/uumgkt.png)
阶梯结构的基本想法是表中的记录对于**不同的数据范围有效,而不是对不同的数据点有效**。这种方法不像索引结构直接,但是要比索引访问节省空间。
## 示例
### 分数
bad
```
let level = '优'
if(score <60 ){
level = '差'
}else if(score < 70) {
level = '一般'
}else if(score < 80) {
level = '中'
}else if(score < 90) {
level = '良'
}
```
good
```
const levelTable = ['差', '中', '良', '优']
const scoreCeilTable = [60, 80, 90, 100]
function getLevel(score) {
const len = scoreCeilTable.length
for(let i = 0; i < len; i++) {
const scoreCeil = scoreCeilTable[i]
if(score <= scoreCeil) {
return levelTable[i]
}
}
return levelTable[len - 1]
}
// 如果需要加一个 60-70 阶段
const levelTable = ['差', '一般', '中', '良', '优']
const scoreCeilTable = [60, 70, 80, 90, 100]
```
### 阶梯访问表需要注意几个问题
1. 留心端点
2. 二分查找替代顺序查找:上面例子用了顺序查找,当数据比较大时,查找成本还是比较大的,应该考虑用二分查找替代顺序查找
3. 考虑用索引访问来取代阶梯技术,阶梯查找比较耗时,如果速度非常重要,可以用索引访问来取代阶梯,用空间换时间,但也要分情况,因为离散空间是不能够完全替代连续空间的
4. 把阶梯表查询操作提取成单独的子程序
';