搜索:merkle树

B

原创 2018-07-23 17:40 阅读(202)次
大规模数据存储中,实现索引查询是在这样一个实际背景下,树单个节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下(为什么会出现这种情况,因为磁盘的操作费时费资源,如果过于频繁的多次查找势必效率低下,详见磁盘读取数据的原理)。 根据磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,那么是不是便能有效减少磁盘查找存取的次数呢?那这种有效的树结构是一种怎样的树呢? 在无法减少查询需求(数据量)的情况下,那么如何减少树的深度,...

Merkle Signature Scheme(merkle

原创 2018-03-26 11:39 阅读(199)次
merkle树是是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构。 Merkle Signature Scheme 是hash密码学中基于merkle树和一次性签名(one-time signatures ,如Lamport signature)的的数字签名方案。 70年代开发,是数字签名算法或者RSA的替代品。 主要的特点是可以抵抗量子计算算法。 传统的公钥算法,如RSA和EIGamal 因为量子计算机(quantum computer)的出现而变得不安全(由于shor's 算法)。 而Merkle Signature Scheme 只依赖于hash...