当前课程知识点:数据结构(Data Structures) > 5. Index > 5.1 Introduction of Index > Video
返回《数据结构(Data Structures)》慕课在线视频课程列表
返回《数据结构(Data Structures)》慕课在线视频列表
各位同学大家好
在接下来的这节课中
我们将学习到
和查找密切相关的索引技术
index
我们首先来看一下
为什么需要索引呢
在现实应用中
我们经常会需要对
存储在磁盘上的大量记录
执行查找操作
比如给定学生的姓名
在所有的学生记录中
查找某个学生的信息
除了要支持查找操作之外
我们经常还需要对数据
进行插入或者删除操作
有时还需要支持范围查找
比如要查找平均成绩
介于80分和90分之间的学生信息
为了方便使用
我们往往还需要支持
多关键字的查找
比如可以按照姓名来查找
也可以按照学号 班级等等信息
来进行查找
那么我们前面学习的
查找技术中主要是用于
在内存中的数据查找
并没有考虑到大量数据
在磁盘中的读写问题
此外我们所学习到的查找方法
比如哈希表技术
只支持精确匹配的查找操作
那它对范围的操作
是支持的不好的
为了去满足前面
我们所说的这些实际需求
我们需要引入索引技术
下面我们给出
索引的常见结构
这幅图给出了索引的结构
我们通常会把原始数据
存储在磁盘上
为了去支持快速的查找
我们会把一些关键字信息
以及数据在磁盘中的存储位置
记录在索引中
所以就有点像我们一本书的目录
而磁盘上的原始数据
就相当于书的内容
所以大小要远远的小于
磁盘中的原始数据
我们可以把部分
或者是全部索引信息
加载到内存中
方便我们在内存中进行查找
一旦我们找到对应的关键字
我们就可以根据索引的指示
到磁盘中去读取完整的数据
为了支持多关键字的查找
我们还可以针对不同的关键字
去构建不同的索引
在设计索引的过程中
我们往往还需要考虑到
对数据的插入
删除以及范围查找
等等这些操作的良好支持
在后面的课程中
我们将会学习到一些
常见的索引技术
其中包括最基本的线性索引技术
以及可以支持高效插入 删除
和查找的树索引技术
包括2-3树和B树
好的 这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video