B-和B+树

### B-树 我们知道B-树每个节点上包含着数据和指针，每个指针指向其一个子节点的位置， B-树的查找需要一次对每个节点进行二分查找，直至找到或返回null。通常，可以引入布朗过滤器等方式加速查找。B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点(其搜索性能等价于在关键字全集内做一次二分查找)。 应用场景： - 一般B-树常常作为磁盘的查找的数据结构使用。 - 一般磁盘为了减少寻道时间，往往会进行预读，一次读入1个或多个page的数据。我们只要将B-树的每个节点控制在一个page大小，就可以保证，磁盘一次的查找只需要一次IO。一个page大小一般在4k，可以存储不少的数据， 假设一个节点存储数据量为100**，**深度为3的B-树，即可保存100w数据(100*100*100)，而100的数据一般用不了4k的存储空间。当然，这里节点中存储的东西主要包括data和指针，指针大小是固定的，而数据有大有小。只要控制好每个数据块的大小，就可以提高B-树的性能。另外，一般情况下非叶子节点占用空间一般较小，完全可以缓存至内存中，这点也是在实际数据库实现中常常使用到的优化。 ### B+树  ### 特点 1. 有n棵子树的节点中含有n个关键字。 1. 所有的叶子结点中包含了全部关键字的信息，及所指向含这些关键字记录的指针，且叶子节点本身依关键字的大小而自小到大的顺序链接。 1. 所有非叶子结点可以看成是索引部分，结点中仅含有其子树中的最大(最小)关键字。 ### NOTE 1. B+树通常有两个指针，一个指向根结点，另一个指向关键字最小的叶子结点。因些，对于B+树进行查找两种运算：一种是从最小关键字起顺序查找，另一种是从根结点开始进行随机查找。 1.  在随机查找时，若非终端结点上的数据等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径 1. B+树的查找与删除都从叶子节点开始 1. B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了 ### 应用场景： 这个结构一般用于数据库的索引，综合效率非常高，像 BerkerlyDB , sqlite , mysql 数据库都使用了这个算法处理索引。如果想自己做个小型数据库，可能参考一下这个算法的实现。索引在数据库中的作用。在数据库系统的使用过程当中，数据的查询是使用最频繁的一种数据操作。当数据库中数据非常多的时候，数据查询的效率就是数据库系统用户最关心的问题。要提高数据查询的效率，最简单、有效的方法就是在数据表相应的列上建立索引。索引是对数据库表中一个或多个列的值进行排序的结构。与在表中搜索所有的行相比，索引用指针指向存储在表中指定列的数据值，然后根据指定的次序排列这些指针，有助于更快地获取信息。通常情况下，只有当经常查询索引列中的数据时，才需要在表上创建索引。索引将占用磁盘空间，并且影响数据更新的速度。但是在多数情况下，索引所带来的数据检索速度优势大大超过它的不足之处。 ### B+树和B-树最大的不同点 1. B-树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。 1. 在B-树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B+树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B+树好，而在实际应用中却是B+树的性能要好些。因为B+树的非叶子节点不存放实际的数据，这样每个节点可容纳的元素个数比B-树多，树高比B-树小，这样带来的好处是减少磁盘访问次数。尽管B+树找到一个记录所需的比较次数要比B-树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中B+树的性能可能还会好些，而且B+树的叶子节点使用指针连接在一起，方便顺序遍历(例如查看一个目录下的所有文件，一个表中的所有记录等)，这也是很多数据库和文件系统使用B+树的缘故。 数据库中集中索引方式。比如一个数据库中存储的是：用户信息(id, age, last_name, hometow)这样的四元组 **hash index：**如果要查询”finding all people with a last name of 'Smith.'”, 可以构造hash表，其key为last_name,而其value为指向某行的指针(也就是整条用户信息)。但是如果要查询"Find all people who are younger than 45."则hash表无能为力了，因为Hashes can deal with equality but not inequality. **bitmap index:**采用这种索引的话，查询效率很高，可以在常数时间内查询，但需要很大的存储空间 **B- index:** The main benefit of a B-tree is that it **allows logarithmic selections, insertions, and deletions in the worst case scenario**.**And unlike hash indexes it stores the data in an ordered way, allowing for faster row retrieval when the selection conditions include things like inequalities or prefixes. **Nodes in a B-tree contain**a value **and **a number of pointers to children nodes.**For database indexes the "**value" is really a pair of values: the indexed field and a pointer to a database row.(but in B+ the value is only an indexed field)**That is,rather than storing the row data right in the index, you store a pointer to the row on disk. B-tree indexes are typically designed so that each node takes up one disk block [](http://en.wikipedia.org/wiki/Block_(data_storage)). This allows each node to be read in with a single disk operation. ### 小结 B树：平衡二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点； B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点； 所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中； B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中； 转载请注明出处：[http://blog.csdn.net/songzitea/article/details/8864192](http://blog.csdn.net/songzitea/article/details/8864192)