假设需要对磁盘上的2000W条记录构建索引，你认为下面哪种数

[单选题]

假设需要对磁盘上的2000W条记录构建索引，你认为下面哪种数据结构来存储索引最合适？

```
Hash Table
```
```
AVL-Tree
```
```
B-Tree
```
```
List
```

查看正确选项

语语嫣嫣

AVL-Tree 检索速度是很快的，这是因为二分检索是树结构的一个本质特性。但是最大的缺点是他的存储利用率太低。每个树节点仅仅有一个数据项，有2个指针和每个数据项的控制信息。

Hash Table当溢出发生时可以分裂成2个节点。目录以2的指数倍增长，只要一个节点溢出而且目录已经达到了指定的最大目录深度，他就会加倍。一个问题就是任何一个节点都能引起目录分裂，因此如果Hash函数不是很随机的话，目录可能增长的很大。

List优点是存取方便，但不便于动态维护，进行插入删除等操作时需要移动大量的数据。

B-tree是比较合适用于磁盘的数据结构，由于他是一个宽而浅的树，查找一个数需要访问很少的节点。内存利用率是比较好的，所以他用于内存数据库比较合适；搜索速度比较快（用二分查找时，只访问很少一部分节点）；而且更新速度也比较快（数据移动通常只涉及到一个节点）

发表于 2019-10-18 11:00:32 回复(0)