HASH与B树的联系与区别？

哈希索引和b树索引，什么情况下，选择哪个索引的有~

楼主这里的哈希索引应该指的是哈希聚簇，楼主可以参考以下两篇文章，写的比较详细：

和

没啥联系。
b树，一种结构，用以存放数据等等。
hash，算法，包括很多种具体的算法（数学逻辑），
db根据hash算出来的值控制数据存放的结构。

1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树，其定义如下：
　　一棵m阶的B树满足下列条件：
　　⑴ 树中每个结点至多有m个孩子；
　　⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；
　　⑶ 若根结点不是叶子结点，则至少有2个孩子；
　　⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；
　　⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字。
　　在B树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。
　　因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。
　　B树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）
　　其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。
　　2. B树的查找:
　　在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,kj查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查的关键字在某个Ki或Ki+1之间，于是取Pi所指的结点继续查找，直到找到，或指针Pi为空时查找失败。
　　查找算法演示
　　性能分析：
　　设B树包含N个关键字，因此有N+1个叶子结点，叶子都在第I层。因为根至少有两个孩子，因此第二层至少有两个结点。除根和叶子外，其它结点至少有┌m/2┐个孩子，因此在第三层至少有2*┌m/2┐个结点，在第四层至少有2*┌m/2┐2个结点，．．．，在第I层至少有2*┌m/2┐I-1 个结点，于是有：
　　N+1 ≥ 2*┌m/2┐I-1
　　即： I ≥ log┌m/2┐( )
　　这个公式保证了B树的查找效率是相当高的。
　　3. B树的插入:
　　当在叶子结点处于第L+1层的B树中插入关键字时，被插入的关键字总是进入第L层的结点。
　　若在一个包含j<m-1个关键字的结点中插入一个新的关键字，则把新的关键字直接插入该结点即可；但若把一个新的关键字插入到包含m-1（m为B树的阶）个关键字的结点中，则将引起结点的分裂。在这种情况下，要把这个结点分裂为两个，并把中间的一个关键字拿出来插到该结点的双亲结点中去，双亲结点也可能是满的，就需要再分裂、再往上插，从而可能导致B树可能朝着根的方向生长。
　　插入算法演示
　　4. B树的删除:
　　当从B树中删除一个关键字Ki时，总的分为以下两种情况：
　　如果该关键字所在的结点不是最下层的非叶子结点，则先需要把此关键字与它在B树中后继对换位置，即以指针Pi所指子树中的最小关键字Y代替Ki，然后在相应的结点中删除Y。
　　如果该关键字所在的结点正好是最下层的非叶子结点，这种情况下，会有以下两种可能：
　　① 若该关键字Ki所在结点中的关键字个数不小于┌m/2┐，则可以直接从该结点中删除该关键字和相应指针即可。
　　② 若该关键字Ki所在结点中的关键字个数小于┌m/2┐，则直接从结点中删除关键字会导致此结点中所含关键字个数小于┌m/2┐-1 。这种情况下，需考察该结点在B树中的左或右兄弟结点，从兄弟结点中移若干个关键字到该结点中来（这也涉及它们的双亲结点中的一个关键字要作相应变化），使两个结点中所含关键字个数基本相同；但如果其兄弟结点的关键字个数也很少，刚好等于┌m/2┐-1 ，这种移动则不能进行，这种情形下，需要把删除了关键字Ki的结点、它的兄弟结点及它们双亲结点中的一个关键字合并为一个结点。

---

潮安县18663125817： HASH与B树的联系与区别?？
薛勉敏迪： 1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树,其定义如下: 一棵m阶的B树满足下列条件: ⑴ 树中每个结点至多有m个孩子; ⑵ 除根结点和叶子结点外,其它每个结点至少有m/2个孩子; ...

潮安县18663125817： HASH与B树的联系与区别? - ？
薛勉敏迪： 展开1全部 1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树,其定义如下: 一棵m阶的B树满足下列条件: ⑴ 树中每个结点至多有m个孩子; ⑵ 除根结点和叶子结点外,其它每个结点至少有m/2...

潮安县18663125817： MySQL B 树索引和哈希索引的区别 - ？
薛勉敏迪： 在MySQL里常用的索引数据结构有B+树索引和哈希索引两种,我们来看下这两种索引数据结构的区别及其不同的应用建议.二者区别 备注:先说下, 在MySQL文档里,实际上是把B+树索引写成了BTREE ,例如像下面这样的写法:CREATE TABLE t( aid int unsigned not null auto_increment,userid int unsigned not null default 0,username varchar(20) not null default '',detail varchar(255) not null default '',

潮安县18663125817： MySQL Hash索引和B - Tree索引的区别 - ？
薛勉敏迪： MySQL Hash索引相对于B-Tree索引,检索效率要高上不少,下文对两者的区别进行了详细的阐述,希望可以让您对MySQL索引有更深的认识. AD: MySQL Hash索引和B-Tree索引的区别究竟在哪里呢?相信很多人都有这样的疑问,下文对两者...

潮安县18663125817： 为什么数据库采用B树,搜索引擎用Hash - ？
薛勉敏迪： 关系型数据库的索引大多采用B/B+树来作为存储结构,而全文检索的搜索引擎则主要采用Hash来作为索引的存储结构,这两类系统的算法都比较成熟了,为什么它们要在各自的应用环境下采用这两种数据结构来存储索引.我个人的理...

潮安县18663125817： mysql数据量大时怎么建立索引提高查询效率 - ？
薛勉敏迪： mysql的索引方法btree和hash的区别 Hash索引:Hash 索引结构的特殊性,其检索效率非常高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些:(1)Hash 索引仅仅能满足”=”,”IN”和”<=>”查询,不能使用范...

潮安县18663125817： 一个表只能有一个主键索引,一个主键索引可以多个字段 - ？
薛勉敏迪： 面试的时候肯定会问这一个问题,mysql为什么会选择b+树作为索引呢?而不选择其他索引,例如b树?hash?下面说的磁盘IO是指数据从硬盘加载到内存中的操作 hash索引的话,不支持范围查询,因为hash就是一个键对应一个值的,没办法范...

潮安县18663125817： oracle数据库索引种类,分别什么情况下使用 - ？
薛勉敏迪： 1. b-tree索引 Oracle数据库中最常见的索引类型是b-tree索引,也就是B-树索引,以其同名的计算科学结构命名.CREATE INDEX语句时,默认就是在创建b-tree索引.没有特别规定可用于任何情况. 2. 位图索引(bitmap index) 位图索引特定...

潮安县18663125817： MySQL BTree索引和hash索引的区别 - ？
薛勉敏迪： 1. hash索引查找数据基本上能一次定位数据,当然有大量碰撞的话性能也会下降.而btree索引就得在节点上挨着查找了,很明显在数据精确查找方面hash索引的效率是要高于btree的; 2. 那么不精确查找呢,也很明显,因为hash算法是基于等值计算的,所以对于“like”等范围查找hash索引无效,不支持; 3. 对于btree支持的联合索引的最优前缀,hash也是无法支持的,联合索引中的字段要么全用要么全不用.提起最优前缀居然都泛起迷糊了,看来有时候放空得太厉害; 4. hash不支持索引排序,索引值和计算出来的hash值大小并不一定一致.

潮安县18663125817： 面试问题:请用白话说明一下Java中HashMap和TreeMap的区别? - ？
薛勉敏迪： HashMap-- 底层是哈希表数据结构,可以存入null键null值,线程不同步的 TreeMap -- 底层是二叉树数据结构,线程不同步,可以给map集合中的键进行排序 HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的).HashMap效率高