RDBMS索引日志

浏览数：15 / 时间：2015年06月12日

一、数据结构

B-tree:

1) 平衡树，子树高度一致，M阶即M叉树

2) 叶节点间相互独立

技术分享

B+TREE：

1) 继承B-TREE

2）n 棵子树的结点中含有n 个key；

3）所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。

4）所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。

技术分享

那么更深层次的区别在哪里：

1. 数据（point/record) 在哪里？如果按b-tree组织，数据有可能在叶节点中，有可能在非叶节点中，对于B+tree，所有数据都在leaf中。

2. 非leaf节点的存储效能

2.1 B-TREE中，不管 non-leaf-NODE(中间层的节点）中存储的是 value的point，还是value的真实record，都需要耗费空间（内存、硬盘）存储这部分point/record

2.2 B+TREE中，non-leaf-node 只存储index,（本身自己还会在leaf中出现，自身的value在leaf中能找到）

2.3 有何意义？　

=> B+TREE每个中间层节点能表达的索引范围更大，系统不管读一次内存/硬盘（例如4K），能得到的索引更多，对于读取多个值的场景，索引查找过程中，内存分页/磁盘扇区复用的概率比B-TREE更高。对于写，B+TREE需要多写几层，也不好说就比B-TREE写的快。

=> seek的过程，B-TREE看运气，可能从ROOT跑到一半就找到值了，B+TREE所有都一样，固定的都需要从ROOT跑到LEAF。

3. 范围查询，可能B+TREE更优秀

例如 col between 100 and 500, 如果是B-TREE, 查找需要2次，100所在点, 500所在的点，然后中序（先序？后序？）遍历这两个点中间的所有NODE,才能得到所有数据（因为数据在NODE内）。如果是B+TREE,只需要找一次，先找到100所在点，然后顺着 LEAF-LinkedNodeList一直往下走，碰到500停下来即可。

二、Leaf-Node的存储方式

1. cluster index

key后面带着的就是record, leaf-node就是data-node, 还有各种说法，例如什么index中key的顺序与data的顺序一致，都是一个意思。

zhangsan: zhangsan, male, 18, class 3, 32012121918231999

wanger: wanger, male, 18, class 3, 32321912831911123

2. non-cluster index

key后面带着的是*recode,或者说地址，或者说point，一个意思。

zhangsan: 0x3211FF12, 或者 4:page707,21, 最后 -> zhangsan, male, 18, class 3, 32012121918231999

wanger: 0x3241D5EB, 或者 17:page707, 22, 最后-> wanger, male, 18, class 3, 32321912831911123

那么区别在哪里？

1. non-cluster scan/seek到了leaf-node, 还需要再 get一次相应 address。而cluste-index不需要

2. non-cluster 中，兄弟（zhangsan,wanger)的index在一起，但实际record 往往不在一起，是否会产生大量缺页中断？而cluster就可以充分的利用os的文件系统的预读特性（顺序读写, not随机读写)，在大量读的场景，效率更高。