当前位置:网站首页>BTREE, B + tree and hash index
BTREE, B + tree and hash index
2022-04-23 07:42:00 【0zien0】
hash Index is characterized by high retrieval efficiency , Search once to locate ,BTree You need to look down from the root node , After many times IO Visit to find the results , therefore hash Indexing is much more efficient than BTree.
but hash It also has many limitations and defects :
1.hash The target can only be accurately located by index , Instead of range query .
2. because hash Only the past is saved hash After calculation hash Value and corresponding line pointer , So it can't be used for sorting .
3.hash If the index encounters a large number of hash Equal values , Then a large amount of record pointer information will be stored in the same hash Value up , In this way, it will be troublesome to locate a record , The final efficiency is not necessarily better than BTree High index .
4. For composite indexes ,hash The index will combine the combined indexes and then calculate hash value , Instead of calculating separately hash value , So by combining the first several index key values of the index ,hash The index cannot be used .
5. Because different index keys may have the same hash value , therefore hash The index cannot avoid full table scanning at any time .
BTree Also called balanced multiple search tree . A tree m Step B Trees (m Fork tree ) Its characteristics are as follows :
1. Each node in the tree contains at most m A child (m>=2);
2. Except for root and leaf nodes , Every other node has at least [ceil(m / 2)] A child ( among ceil(x) It's a function with an upper bound );
3. If the root node is not a leaf node , At least 2 A child ( A special case : No child's roots , That is, the root node is the leaf node , The whole tree has only one root node );
4. All leaf nodes appear in the same layer , Leaf node does not contain any keyword information
5. Each non terminal node contains n Keyword information (P0,P1,…Pn, k1,…kn)
6. Number of keywords n Satisfy :ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n) Keyword , And the keywords are sorted in ascending order .
8. Pi(i=1,…n) Is the pointer to the root node of the subtree .P(i-1) All node keywords of the pointed subtree are less than ki, But they are greater than k(i-1)
B+Tree Is in BTree An optimization based on .
1. Non leaf nodes only store key information . This can greatly increase the storage capacity of each node key Value quantity , Reduce B+Tree Height .
2. There is a chain pointer between all leaf nodes . Traversal is more convenient .
3. Data records are stored in leaf nodes .
Reference material :
Contains a binary tree 、 Balanced binary trees 、 Balance multiple search trees (BTree)
https://blog.csdn.net/hao65103940/article/details/89032538
版权声明
本文为[0zien0]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230623293861.html
边栏推荐
猜你喜欢
Nacos / sentinel gateway current limiting and grouping (code)
Mysql持久性的实现
反思|开启B站少女心模式,探究APP换肤机制的设计与实现
Reflect on the limitations of event bus and the design and implementation of communication mechanism in component development process
如何SQL 语句UNION实现当一个表中的一列内容为空时则取另一个表的另一列
数据分析入门 | kaggle泰坦尼克任务(三)—>探索数据分析
保洁阿姨都能看懂的中国剩余定理和扩展中国剩余定理
Date对象(js内置对象)
快速下载vscode的方法
SAP PI/PO Soap2Proxy 消费外部ws示例
随机推荐
VScode
5. Sql99 standard: internal connection and external connection
快速傅里叶变换FFT简明教程
Authorization server (simple construction of authorization server)
12.约束
常用的DOS命令
[2020WC Day2]F.采蘑菇的克拉莉丝(子树和查询、轻重儿子思想)
技术小白的第一篇(表达自己)
xdotool按键精灵
What is a closure?
自定义时间格式(YYYY-MM-DD HH:mm:ss 星期X)
9.常用函数
Django使用mysql数据库报错解决
状态同步与帧同步
保洁阿姨都能看懂的中国剩余定理和扩展中国剩余定理
技能点挖坑
Source Insight 4.0常见问题
14.事务处理
vim+ctags+cscpope开发环境搭建指南
13.用户和权限管理