当前课程知识点：数据结构（Data Structures） > 5. Index > 5.3 2-3 tree index > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
下面我们将学习到
一种树形索引2-3树
那么什么是树索引呢
和线性索引不同的是
树索引里面的所有索引单元
都是根据关键字
来组成一个树形结构
在进行关键字查找的时候
索引结构里面的关键字来进行比对
从而选择合适的分支
最终定位到磁盘的记录
那么什么样的树结构
可以去胜任高效的
查找插入以及删除操作呢
我们之前学习过的
二叉查找树BST
可以作为一个备选方案
我们知道当BST处于一个
平衡状态的时候
那么在BST上面
进行查找 插入和删除操作
它的复杂度都是⊙（log n）
这是比较高效的
然而我们看到BST
它其实并不是一个
特别理想的选择
这是因为
我们要让BST始终保持平衡状态
往往需要付出比较大的调整代价
比如在下面这个例子中
左侧的BST
它是一个完全二叉树
处于一种平衡的状态
当我们要在里面
插入一个结点1的时候
为了不去破坏树的平衡
我们还要将它调整成为
一个完全二叉树
我们对比一下
调整前后
树上结点的变化
我们发现大多数结点的位置
发生了改变
这就意味着
我们需要花费比较大的代价
来去完成这个调整
那么什么样的树结构
更加适合用来去做索引呢
下面我们来学习一下
2-3树这种索引结构
所谓的2-3树
是具有下面这些性质的树结构
首先树里面的每一个结点
包含有一个或者是两个关键字
相应的每一个中间结点
它包含有两个或者三个孩子
对于任意一个
有三个孩子的结点来说
最左边这个分支
它的子树上所有的结点的值
都要小于这个结点的
第一个关键字
而中间分支上的所有结点的值
都要大于等于第一个关键字
而小于第二个关健字
而最右边分支上的所有结点的值
都要大于等于第二个关键字的值
对于有两个孩子的结点来说
它就只有一个关键字
而且这个关键字的值
要大于左子树上的结点的值
并且小于等于右子树上的结点的值
另外还有一个性质
就是树上所有的叶子
都始终保持在同一个层次上
所以我们说2-3树
它是一种始终能够
保持高度平衡的树
下面我们来看一下在2-3树上面
如何进行查找
实际在2-3树上面的查找过程
类似于在BST上面的查找
我们首先会把要查找的关键字
和树根的关键字进行比较
比如在这个例子里面
我们要找的是21
我们发现21不在树干里面
我们就把21和树根的关键字进行比较
我们知道21要大于
第一个关键字18
同时小于第二个关键字33
所以我们将在中间的分支里面
去查找21
我们继续把21
和中间的孩子结点的关键字进行比较
我们发现21小于第一个关键字
所以我们将继续地
在最左边的分支里面去查找
最后我们在叶子结点
找到了这个关键字
类似于BST的查找过程
我们从树根出发
然后沿着一条路径
然后到达某个结点
整个查找过程
我们要查找的结点的数目
不会超过整棵树的高度
而我们可以证明
对有n个结点的2-3树来说
它的高度是等于⊙（log n）的
所以这个查找过程
它的时间复杂度
同样也是⊙（log n）
这个查找效率和平常
二叉查找树的效率
是同一个量级
下面我们再来看一下
在2-3树上面的插入操作
我们先来看一个简单的例子
在这个例子中
我们要插入的关键字是14
类似于前面的查找过程
我们将从树根出发
然后去查找适合插入14的位置
因为14比18小
所以我们插入最左边的分支
然后14比12大
所以我们插入中间的分支
最终我们找到了
某个叶子结点的位置
而这个叶子结点
恰恰只有一个关键字
还有一个空位
所以我们可以把14
插入到这个结点的
合适位置上面去
下面我们再来看一个
复杂一点的例子
在这棵2-3树中
我们要插入关键字19
那么通过关键字比较
我们确定19应该插入到
最左边的叶子中去
但是我们看到
这个叶子它已经满了
无法再插入更多的结点
所以在这种情况下
我们要进行结点的分裂
把原来的结点分裂成为两个结点
去存放这三个关键字
其中分裂出来的
最左边的这个结点
保存最小的关键字
最右边的结点
保存最大的关键字
还有一个中间的关键字
我们要把它继续地插入到
父亲结点中去
如果这个时候
父亲结点还没有满
我们就可以将这个中间的关键字
插入到合适的位置中去
并且让父亲结点
和分裂出来的孩子结点
建立相应的联边
在这个例子中
刚好还没有满
所以还可以继续增加关键字
那么如果父亲结点它已经满了
又应该怎么办呢
下面我们来看一下
父亲结点为满的情况
在这里我们要插入关键字19
同样地
我们首先要确定插入的位置
也就是这里的叶子结点
由于这个结点是满的
所以我们要进行一个
结点的分裂
分裂之后产生的中间关键字
将会插入到父亲结点中去
但是我们会看到
这个时候父亲结点它也是满的
如果我们把这个关键字
强行地插入进去
我们将会得到这样的一棵树
在这里面这棵树
它是不满足2-3树的要求的
父亲结点已经超负荷了
同样它需要分裂
这个分裂的过程
将会产生两个中间结点
其中左边的结点
会存放最小的关键字
右边结点存放最大的关键字
中间的关健字
将会继续地插入到
更高一层的父亲结点上面去
这个插入的过程
可能会导致持续的分裂
并且产生一个插入到
上层结点的关键字
直到某次插入它没有发生分裂
那么就会停止
这个持续分裂的过程
整个过程中
插入和分裂的次数
它是不会超过整个树的高度的
所以消耗的时间是
⊙（log n）的量级
因此我们在这里可以看到
相对BST来说
2-3树可以以较小的代价
完成关键字的插入查找
并且时刻保持平衡
所以它更适合用来
去构造数据的索引
好的 我们这节课讲到这里
-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
