数据结构(四) B树/跳表
目录
1. LRU
2. B树
3. 跳表
1. LRU:
1.1 概念:
最近最少使用算法, 就是cache缓存的算法. 因为cache(位于内存和cpu之间的存储设备)是一种容量有限的缓存, 有新的数据进入就需要将原本的数据进行排出.
1.2 LRU cache实现:
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
class LRUCache
{
public:
LRUCache(int capacity)
{
_capacity = capacity;
}
//获取数据.
int get(int key)
{
//找到数据key的值.
auto hashit = _hashmap.find(key);
if(hashit != _hashmap.end())
{
//找到对应关键词
auto listit = hashit->second;
pair<int, int> kv = *listit;
//删除原来对应关键词数据;
_list.erase(listit);
//现在头插关键词数据.
_list.push_front(kv);
//然后改变一下hashmap的key的值..
_hashmap[key] = _list.begin();
return kv.second;
}
else
{
return -1;
}
}
//插入新的数据.key,value类型的.
void put(int key, int value)
{
auto hashit = _hashmap.find(key);
if(hashit == _hashmap.end())
{
//找不到对应的数据;
if(_list.size() >= _capacity)
{
//大于容量.
_hashmap.erase(_list.back().first);
//删除最后一个数据.(这个数据很久没访问过的);
_list.pop_back();
}
_list.push_front(make_pair(key, value));
_hashmap[key] = _list.begin();
}
else
{
auto listit = hashit->second;
pair<int, int> kv = *listit;
kv.second = value;
_list.erase(listit);
_list.push_front(kv);
_hashmap[key] = _list.begin();
}
}
private:
//链表保存各个cache里的数据.
list<pair<int, int>> _list;
size_t _capacity;
//使用下标和cache数据指针进行映射.
unordered_map<int, list<pair<int, int>>::iterator> _hashmap;
};2. B树:
2.1 常见的搜索结构:
顺序查找O(N), 二分查找O(logN), 二叉搜索树O(N), 二叉平衡树O(logN), 哈希O(1);
这些查找算法只能在数据量比较少, 以及内存可以一次进行寻找的, 如果数据量很大, 那么数据一次无法放到内存只能在磁盘中. 那么内存和磁盘进行交互的话时间就比较慢.
2.2 B树的概念:
一种平衡多叉树, 可以进行外查找的. 一棵M阶多叉树, 是一个平衡M路的平衡多叉树.满足性质:
(1) 根结点至少有两个孩子;
(2) 每个分支结点都包含k-1个关键字和k个孩子. 其中k的取值在[m/2, m]之间.
(3) 每个叶子结点都包含k-1个关键词; k的取值[m/2, m];
(4) 叶子结点都在一层, (5) 每个结点从小到大排序.
2.3 B树的插入分析:
下面拿三叉树来举例, M = 3, 那么每个结点可以最多存储2个数据(k范围[1, 3), k-1个关键词; 孩子的话永远比数据多一个, 就是3个孩子.
插入数据74, 49, 139, 145, 36, 53的过程. 如果结点满就需要分裂.
2.4 B树的实现:
(1) 结构:
采用一个关键词数组以及存放关键词的孩子结点, 还有一个保存关键词的父亲结点.
//类型为k, 数量为M.
//M层数.
template<class K, size_t M>
struct BTreeNode
{
//创建关键词数组; 以及相对应的孩子结点.
K _keys[M];
//孩子结点的指针.
BTreeNode<K, M>* _subs[M+1];
BTreeNode<K, M>* _parent;
//记录存储关键字数.
size_t _n;
BTreeNode()
{
for(size_t i = 0; i < M; i++)
{
_keys[i] = K();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
_parent = nullptr;
_n = 0;
}
};
template<class K, size_t M>
class BTree
{
typedef BTreeNode<K, M> Node;
private:
Node* _root = nullptr;
};(2) 查找:
//查找数据:
pair<Node*, int> Find(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
//遍历B树结点.
while(cur)
{
size_t i = 0;
while(i < cur->_n)
{
//小于关键词不存在.
if(key < cur->_keys[i])
{
break;
}
//大于就在右边.
else if(key > cur->_keys[i])
{
i++;
}
else
{
//相等返回cur结点以及下标位置.
return make_pair(cur, i);
}
}
//本关键词找不到就到另外一个关键词查看.
parent = cur;
cur = cur->subs[i];
}
//找不到就返回空.
return make_pair(parent, -1);
}(3) 插入关键字:
如果满了首先找到中间结点, 中间结点的后面结点移动新结点, 然后中间结点放到parent数组中.
//(4) 遍历关键词:
遍历每个结点的孩子结点, 先左子树, 再根, 后右子树即可.
void _InOrder(Node* cur)
{
if(cur == nullptr)
return;
size_t i = 0;
for(; i < cur->_n; i++)
{
//先遍历左子树.
_InOrder(cur->_subs[i]);
//打印根子树.
cout << cur->_keys[i] << " ";
}
//再去遍历右子树.
_InOrder(cur->_subs[i]);
}(5) B树性能分析:
查找效率大概就是O(logM-1)到O(logm/2); 查询到结点就再使用二分查找很快就可以找到. l例如620亿个数据, 树的度是1024的话, 最多需要查询4次. 这样就可以减少磁盘io次数.
2.5 B+树:
在B树上做了些修改: (1) 分支节点的子树指针和关键字个数相同;
(2) 叶子结点增加一个连接指针将叶子结点连接在一起.
(3) 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
(4) 所有关键字及其映射数据都在叶子节点出现
所有的关键字都出现在叶子结点的链表中, 并且有序;
不可能在分支结点命中, 分支结点相当与是叶子结点的索引, 叶子结点才是真正存储数据的.
B+树的增加只会改变原结点以及父结点, 因为将一半结点给兄弟结点, 源节点给父亲结点即可.
2.6 B*树:
B+树的变形, 增加非叶子结点和非根结点的链表指针.
B*树增加数据就要将看兄弟结点没满就将数据插入到兄弟结点中, 其次就是满的话将数据创建一个新的结点, 然后将1/3数据给新结点, 重新修改一下父结点的指向孩子的指针.
2.6 总结:
(1) B树: 有序数组和平衡多叉树;
(2) B+树: 有序数组链表和平衡多叉树;
(3) B*树: 一个饱满, 均匀, 空间利用率高的B+树.
2.7 B树的运用:
在MySQL中使用到索引, 高效获取数据的数据结构, 索引在于表, 而不是数据库.
(1) MyISAM: (非聚簇索引)
不支持事务, 支持全文索引, 叶子结点存放的是数据的地址. 包含主索引和辅助索引, 主索引的key不能重复, 辅助索引可以. 这种数据和索引不在一起的就是非聚簇索引.
(2) Innodb:
支持事务, 支持B+树索引、全文索引、哈希索引。它是将数据和索引存放在一起; 数据存储的是值不是地址, 这种就是聚簇索引.
