B-Tree index 也是我们传统上常见所理解的索引。 B-tree ( balance tree )即平衡树,左右两个分支相对平衡。
B-Tree index
Root 为根节点, branch 为分支节点, leaf 到最下面一层称为叶子节点。每个节点表示一层,当查找某一数据时先读根节点,再读支节点,最后找到叶子节点。 叶子节点会存放 index entry (索引入口),每个索引入口对应一条记录。
Index entry 的组成部分:
Indexentry entry header 存放一些控制信息。
Key column length 某一 key 的长度
Key column value 某一个 key 的值
ROWID 指针,具体指向于某一个数据