中华智能自建代理网站,济南专业做网站的公司哪家好,建设工作室网站,网站404页面查询目录
1. LRU
2. B树
3. 跳表 1. LRU:
1.1 概念: 最近最少使用算法, 就是cache缓存的算法. 因为cache(位于内存和cpu之间的存储设备)是一种容量有限的缓存, 有新的数据进入就需要将原本的数据进行排出. 1.2 LRU cache实现: #include iostream
#include list…目录
1. LRU
2. B树
3. 跳表 1. LRU:
1.1 概念: 最近最少使用算法, 就是cache缓存的算法. 因为cache(位于内存和cpu之间的存储设备)是一种容量有限的缓存, 有新的数据进入就需要将原本的数据进行排出. 1.2 LRU cache实现: #include iostream
#include list
#include unordered_mapusing 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;pairint, 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;pairint, int kv *listit;kv.second value;_list.erase(listit);_list.push_front(kv);_hashmap[key] _list.begin();}}private://链表保存各个cache里的数据.listpairint, int _list;size_t _capacity;//使用下标和cache数据指针进行映射.unordered_mapint, listpairint, 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层数.
templateclass K, size_t M
struct BTreeNode
{//创建关键词数组; 以及相对应的孩子结点.K _keys[M];//孩子结点的指针.BTreeNodeK, M* _subs[M1];BTreeNodeK, 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;}
};templateclass K, size_t M
class BTree
{typedef BTreeNodeK, M Node;private:Node* _root nullptr;
}; (2) 查找: //查找数据:pairNode*, 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[i1])区间之间 (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树索引、全文索引、哈希索引。它是将数据和索引存放在一起; 数据存储的是值不是地址, 这种就是聚簇索引. 3. 跳表:
3.1 概念:
