基于SSD的新型索引设计

论文总字数：25414字

摘 要

04012138 江磊

指导老师 高晓沨

本文针对固态硬盘上的索引结构的改进工作进行了分析和比较。

如今基于闪存的固态硬盘（Hard Disc Drive，HDD）在数据存储系统中变得越来越常见。为了在固态硬盘中同样保存高效，必须对传统索引进行重新设计以适应闪存的独特特性，例如读写延迟的不平衡（读取快而写入慢）以及异地更新（out-of-place update）。本文主要研究的就是根据固态硬盘的特点，进行索引结构的优化。本论文的主要工作如下：

1、介绍了现在的各种存储介质，展示了固态硬盘的独特特性。

2、介绍了传统的B树索引结构，解释了为何它适用于传统存储介质。

3、介绍了对于固态硬盘上的数据库系统，对传统索引结构进行改进的必要性，并对现有的优化工作进行了总结归纳。

4、选取现有优化工作中有代表性的几个，利用均摊分析，对其索引结构的搜索过程和插入过程计算花销，并将这几种索引结构进行比较。

关键词：固态硬盘，索引，B 树，摊还分析

Abstract

This paper mainly analyzes and compares the optimization of indexing structure on SSD.

Flash-memory-based solid-state drives (SSDs) are used widely in data storage system. To be effective for SSDs, traditional indices have to be redesigned to cope with the special properties of flash memory, such as asymmetric read/write latencies (fast reads and slow writes) and out-of-place updates. This paper mainly researches on the optimization of indexing structure according to the feature of SSD.

The main work is as follows:

1.Introduce current storage device and the special feature of SSD.

2.Introduce traditional B-tree structure and explain why it is suitable for traditional storage device.

3.Introduce the necessity to optimize traditional indexing structure on SSD and conclude the related work.

4.Choose a few representative optimized indexing structures and calculate the cost of search and insertion of them with amortized analysis. It also compares the few structures according to the result.

Keywords: SSD，indexing，B tree，amortized analysis

目录

摘 要 1

Abstract 3

目录 5

第一章 绪论 7

第二章 存储介质 7

2.1机械硬盘（Hard Disc Drive，HDD） 7

2.2闪存（flash） 8

2.2.1特性 8

2.2.2分类 8

2.3固态硬盘（Solid State Disk，SSD） 8

2.4 内存（memory） 10

2.5内存、固态硬盘、机械硬盘的对比 11

第三章 B树索引技术 11

3.1 基本概念 11

3.2 B树 11

3.3 B 树 13

3.4 优势 13

第四章 优化工作 14

4.1 必要性 14

4.2 针对闪存索引的优化 14

4.3 针对固态硬盘索引的优化 16

4.3.1基于更新缓冲的索引 16

4.3.2基于连续写入的索引 17

4.3.3基于溢出页的索引 18

4.3.4基于布伦过滤器的索引 18

第五章 花销分析 20

5.1符号声明 20

5.2 B 树 20

5.2.1 搜索 20

5.2.2 插入 20

5.3 BFTL 21

5.3.1 简介 21

5.3.2 搜索 22

5.3.3 插入 22

5.4 FD树 23

5.4.1 简介 23

5.4.2 搜索花销 24

5.4.3插入花销 24

5.5 Bloom树 26

5.5.1简介 26

5.5.2布伦过滤器的影响 27

5.5.3搜索花销 28

5.5.4插入花销 30

5.6比较 30

第六章 结论 31

致谢 31

参考文献（Reference） 32

第一章 绪论

数据库索引是一种在数据库中改善数据检索操作速度的数据结构。它为快速随机查找和高效访问有序记录提供了基础。数据库系统中通常使用的传统索引结构时B树以及它的变种。因为它适应了传统存储设备机械硬盘的特点。

如今基于闪存的固态硬盘（Hard Disc Drive，HDD）在数据存储系统中变得越来越常见。为了在固态硬盘中同样保存高效，必须对传统索引进行重新设计以适应闪存的独特特性，例如读写延迟的不平衡（读取快而写入慢）以及异地更新（out-of-place update）。本文主要研究的就是根据固态硬盘的特点，进行索引结构的优化。

下面介绍本文余下部分的结构安排：

第二章介绍了现在的各种存储介质，展示了固态硬盘的独特特性

第三章介绍了传统的B树索引结构，解释了为何它适用于传统存储介质。

第四章介绍了对于固态硬盘上的数据库系统，对传统索引结构进行改进的必要性，并对现有的优化工作进行了总结归纳。

第五章选取现有优化工作中有代表性的几个，利用均摊分析，对其索引结构的搜索过程和插入过程计算花销，并将这几种索引结构进行比较。

第六章为结论部分，总结了本文所做的工作。

第二章 存储介质

2.1机械硬盘（Hard Disc Drive，HDD）

机械硬盘指的即是传统硬盘。自上世纪八十年代以来，机械硬盘就被用作主要的数据存储介质。其原理图如下所示。它包含了一个或多个绕主轴旋转的盘片。它们以共同的速度围绕着一个共同的主轴旋转。每个盘的表面覆盖着一层可磁化的物质。硬盘通过磁臂（arm）末尾的磁头（head）来读/写盘片。当读/写磁头静止时，由它下方经过的磁盘表面就是称为一个磁道（track）。磁盘的盘片通过不停旋转，使得磁头可以读取盘片上不同扇区上的数据。多个盘片增加的仅仅是磁盘驱动器的容量，而不影响性能。

剩余内容已隐藏，请支付后下载全文，论文总字数：25414字