sungine
- 浏览: 27965 次
- 性别:
- 来自: 北京
-
最新评论
学习来源:http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
B-树、B+树、B*树
之所以关注这个问题有两个原因:
1.oracle的索引组织表(IOT)是用B-树管理的
2.上次面试时被问到了这个问题,没有完全答出来
二叉树内容 略
B树 B-树
异名 同体 指的是一种多路搜索树
简单总结其特点 就是
1.每个节点的关键字数量是有 上下限要求的 取决于M(大约为M的一半),且关键字是从小到大的
2.然后每个节点的指针数量是关键字个数+1
3.指针的指向原则是,根据关键字划分数学区间(左开右开),分配其子节点,再按从小到大顺序安排指针与子节点的对应关系
4.关键字存在节点上,找到就可取
B+树 
与 B-树 大致类似 区别在于 一个思路的变化:
B+树考虑到某些关键字太过复杂不适合存储在 节点上,于是便把所有关键字放到 树结构的最底层
叶节点存储
如此便有一系列的变化:
1.关键字树与指针树相等
2.指针的指向原则改为,关键子划分的数学区间为左闭右开区间
3.在父命中时 也要到叶节点取数据
B*树
B+多了就变成*了
为了达到增加树结构的使用率(降低分裂的消耗)的目的
对每个节点增加了一个指针,指向其同级 兄弟节点,这样在分裂时,节点需要对 父,兄弟,及自身负责,多方考察完资源后 ,再确定分裂的方式,降低了分裂概率
引用小结
引用
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于
走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率
从1/2提高到2/3；
走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率
从1/2提高到2/3；
附件:B+tree 的Java实现
package com.meidusa.test;
public interface B {
public Object get(Comparable key); //查询
public void remove(Comparable key); //移除
public void insertOrUpdate(Comparable key, Object obj); //插入或者更新，如果已经存在，就更新，否则插入
}
package com.meidusa.test;
import java.util.Random;
public class BplusTree implements B {
/** 根节点 */
protected Node root;
/** 阶数，M值 */
protected int order;
/** 叶子节点的链表头*/
protected Node head;
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public int getOrder() {
return order;
}
public void setOrder(int order) {
this.order = order;
}
@Override
public Object get(Comparable key) {
return root.get(key);
}
@Override
public void remove(Comparable key) {
root.remove(key, this);
}
@Override
public void insertOrUpdate(Comparable key, Object obj) {
root.insertOrUpdate(key, obj, this);
}
public BplusTree(int order){
if (order < 3) {
System.out.print("order must be greater than 2");
System.exit(0);
}
this.order = order;
root = new Node(true, true);
head = root;
}
//测试
public static void main(String[] args) {
BplusTree tree = new BplusTree(6);
Random random = new Random();
long current = System.currentTimeMillis();
for (int j = 0; j < 100000; j++) {
for (int i = 0; i < 100; i++) {
int randomNumber = random.nextInt(1000);
tree.insertOrUpdate(randomNumber, randomNumber);
}
for (int i = 0; i < 100; i++) {
int randomNumber = random.nextInt(1000);
tree.remove(randomNumber);
}
}
long duration = System.currentTimeMillis() - current;
System.out.println("time elpsed for duration: " + duration);
int search = 80;
System.out.print(tree.get(search));
}
}
package com.meidusa.test;
import java.util.Random;
public class BplusTree implements B {
/** 根节点 */
protected Node root;
/** 阶数，M值 */
protected int order;
/** 叶子节点的链表头*/
protected Node head;
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public int getOrder() {
return order;
}
public void setOrder(int order) {
this.order = order;
}
@Override
public Object get(Comparable key) {
return root.get(key);
}
@Override
public void remove(Comparable key) {
root.remove(key, this);
}
@Override
public void insertOrUpdate(Comparable key, Object obj) {
root.insertOrUpdate(key, obj, this);
}
public BplusTree(int order){
if (order < 3) {
System.out.print("order must be greater than 2");
System.exit(0);
}
this.order = order;
root = new Node(true, true);
head = root;
}
//测试
public static void main(String[] args) {
BplusTree tree = new BplusTree(6);
Random random = new Random();
long current = System.currentTimeMillis();
for (int j = 0; j < 100000; j++) {
for (int i = 0; i < 100; i++) {
int randomNumber = random.nextInt(1000);
tree.insertOrUpdate(randomNumber, randomNumber);
}
for (int i = 0; i < 100; i++) {
int randomNumber = random.nextInt(1000);
tree.remove(randomNumber);
}
}
long duration = System.currentTimeMillis() - current;
System.out.println("time elpsed for duration: " + duration);
int search = 80;
System.out.print(tree.get(search));
}
}
package com.meidusa.test;
import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
public class Node {
/** 是否为叶子节点 */
protected boolean isLeaf;
/** 是否为根节点*/
protected boolean isRoot;
/** 父节点 */
protected Node parent;
/** 叶节点的前节点*/
protected Node previous;
/** 叶节点的后节点*/
protected Node next;
/** 节点的关键字 */
protected List<Entry<Comparable, Object>> entries;
/** 子节点 */
protected List<Node> children;
public Node(boolean isLeaf) {
this.isLeaf = isLeaf;
entries = new ArrayList<Entry<Comparable, Object>>();
if (!isLeaf) {
children = new ArrayList<Node>();
}
}
public Node(boolean isLeaf, boolean isRoot) {
this(isLeaf);
this.isRoot = isRoot;
}
public Object get(Comparable key) {
//如果是叶子节点
if (isLeaf) {
for (Entry<Comparable, Object> entry : entries) {
if (entry.getKey().compareTo(key) == 0) {
//返回找到的对象
return entry.getValue();
}
}
//未找到所要查询的对象
return null;
//如果不是叶子节点
}else {
//如果key小于等于节点最左边的key，沿第一个子节点继续搜索
if (key.compareTo(entries.get(0).getKey()) <= 0) {
return children.get(0).get(key);
//如果key大于节点最右边的key，沿最后一个子节点继续搜索
}else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) {
return children.get(children.size()-1).get(key);
//否则沿比key大的前一个子节点继续搜索
}else {
for (int i = 0; i < entries.size(); i++) {
if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) {
return children.get(i).get(key);
}
}
}
}
return null;
}
public void insertOrUpdate(Comparable key, Object obj, BplusTree tree){
//如果是叶子节点
if (isLeaf){
//不需要分裂，直接插入或更新
if (contains(key) || entries.size() < tree.getOrder()){
insertOrUpdate(key, obj);
if (parent != null) {
//更新父节点
parent.updateInsert(tree);
}
//需要分裂
}else {
//分裂成左右两个节点
Node left = new Node(true);
Node right = new Node(true);
//设置链接
if (previous != null){
previous.setNext(left);
left.setPrevious(previous);
}
if (next != null) {
next.setPrevious(right);
right.setNext(next);
}
if (previous == null){
tree.setHead(left);
}
left.setNext(right);
right.setPrevious(left);
previous = null;
next = null;
//左右两个节点关键字长度
int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;
int rightSize = (tree.getOrder() + 1) / 2;
//复制原节点关键字到分裂出来的新节点
insertOrUpdate(key, obj);
for (int i = 0; i < leftSize; i++){
left.getEntries().add(entries.get(i));
}
for (int i = 0; i < rightSize; i++){
right.getEntries().add(entries.get(leftSize + i));
}
//如果不是根节点
if (parent != null) {
//调整父子节点关系
int index = parent.getChildren().indexOf(this);
parent.getChildren().remove(this);
left.setParent(parent);
right.setParent(parent);
parent.getChildren().add(index,left);
parent.getChildren().add(index + 1, right);
setEntries(null);
setChildren(null);
//父节点插入或更新关键字
parent.updateInsert(tree);
setParent(null);
//如果是根节点
}else {
isRoot = false;
Node parent = new Node(false, true);
tree.setRoot(parent);
left.setParent(parent);
right.setParent(parent);
parent.getChildren().add(left);
parent.getChildren().add(right);
setEntries(null);
setChildren(null);
//更新根节点
parent.updateInsert(tree);
}
}
//如果不是叶子节点
}else {
//如果key小于等于节点最左边的key，沿第一个子节点继续搜索
if (key.compareTo(entries.get(0).getKey()) <= 0) {
children.get(0).insertOrUpdate(key, obj, tree);
//如果key大于节点最右边的key，沿最后一个子节点继续搜索
}else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) {
children.get(children.size()-1).insertOrUpdate(key, obj, tree);
//否则沿比key大的前一个子节点继续搜索
}else {
for (int i = 0; i < entries.size(); i++) {
if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) {
children.get(i).insertOrUpdate(key, obj, tree);
break;
}
}
}
}
}
/** 插入节点后中间节点的更新 */
protected void updateInsert(BplusTree tree){
validate(this, tree);
//如果子节点数超出阶数，则需要分裂该节点
if (children.size() > tree.getOrder()) {
//分裂成左右两个节点
Node left = new Node(false);
Node right = new Node(false);
//左右两个节点关键字长度
int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;
int rightSize = (tree.getOrder() + 1) / 2;
//复制子节点到分裂出来的新节点，并更新关键字
for (int i = 0; i < leftSize; i++){
left.getChildren().add(children.get(i));
left.getEntries().add(new SimpleEntry(children.get(i).getEntries().get(0).getKey(), null));
children.get(i).setParent(left);
}
for (int i = 0; i < rightSize; i++){
right.getChildren().add(children.get(leftSize + i));
right.getEntries().add(new SimpleEntry(children.get(leftSize + i).getEntries().get(0).getKey(), null));
children.get(leftSize + i).setParent(right);
}
//如果不是根节点
if (parent != null) {
//调整父子节点关系
int index = parent.getChildren().indexOf(this);
parent.getChildren().remove(this);
left.setParent(parent);
right.setParent(parent);
parent.getChildren().add(index,left);
parent.getChildren().add(index + 1, right);
setEntries(null);
setChildren(null);
//父节点更新关键字
parent.updateInsert(tree);
setParent(null);
//如果是根节点
}else {
isRoot = false;
Node parent = new Node(false, true);
tree.setRoot(parent);
left.setParent(parent);
right.setParent(parent);
parent.getChildren().add(left);
parent.getChildren().add(right);
setEntries(null);
setChildren(null);
//更新根节点
parent.updateInsert(tree);
}
}
}
/** 调整节点关键字*/
protected static void validate(Node node, BplusTree tree) {
// 如果关键字个数与子节点个数相同
if (node.getEntries().size() == node.getChildren().size()) {
for (int i = 0; i < node.getEntries().size(); i++) {
Comparable key = node.getChildren().get(i).getEntries().get(0).getKey();
if (node.getEntries().get(i).getKey().compareTo(key) != 0) {
node.getEntries().remove(i);
node.getEntries().add(i, new SimpleEntry(key, null));
if(!node.isRoot()){
validate(node.getParent(), tree);
}
}
}
// 如果子节点数不等于关键字个数但仍大于M / 2并且小于M，并且大于2
} else if (node.isRoot() && node.getChildren().size() >= 2
||node.getChildren().size() >= tree.getOrder() / 2
&& node.getChildren().size() <= tree.getOrder()
&& node.getChildren().size() >= 2) {
node.getEntries().clear();
for (int i = 0; i < node.getChildren().size(); i++) {
Comparable key = node.getChildren().get(i).getEntries().get(0).getKey();
node.getEntries().add(new SimpleEntry(key, null));
if (!node.isRoot()) {
validate(node.getParent(), tree);
}
}
}
}
/** 删除节点后中间节点的更新*/
protected void updateRemove(BplusTree tree) {
validate(this, tree);
// 如果子节点数小于M / 2或者小于2，则需要合并节点
if (children.size() < tree.getOrder() / 2 || children.size() < 2) {
if (isRoot) {
// 如果是根节点并且子节点数大于等于2，OK
if (children.size() >= 2) {
return;
// 否则与子节点合并
} else {
Node root = children.get(0);
tree.setRoot(root);
root.setParent(null);
root.setRoot(true);
setEntries(null);
setChildren(null);
}
} else {
//计算前后节点
int currIdx = parent.getChildren().indexOf(this);
int prevIdx = currIdx - 1;
int nextIdx = currIdx + 1;
Node previous = null, next = null;
if (prevIdx >= 0) {
previous = parent.getChildren().get(prevIdx);
}
if (nextIdx < parent.getChildren().size()) {
next = parent.getChildren().get(nextIdx);
}
// 如果前节点子节点数大于M / 2并且大于2，则从其处借补
if (previous != null
&& previous.getChildren().size() > tree.getOrder() / 2
&& previous.getChildren().size() > 2) {
//前叶子节点末尾节点添加到首位
int idx = previous.getChildren().size() - 1;
Node borrow = previous.getChildren().get(idx);
previous.getChildren().remove(idx);
borrow.setParent(this);
children.add(0, borrow);
validate(previous, tree);
validate(this, tree);
parent.updateRemove(tree);
// 如果后节点子节点数大于M / 2并且大于2，则从其处借补
} else if (next != null
&& next.getChildren().size() > tree.getOrder() / 2
&& next.getChildren().size() > 2) {
//后叶子节点首位添加到末尾
Node borrow = next.getChildren().get(0);
next.getChildren().remove(0);
borrow.setParent(this);
children.add(borrow);
validate(next, tree);
validate(this, tree);
parent.updateRemove(tree);
// 否则需要合并节点
} else {
// 同前面节点合并
if (previous != null
&& (previous.getChildren().size() <= tree.getOrder() / 2 || previous.getChildren().size() <= 2)) {
for (int i = previous.getChildren().size() - 1; i >= 0; i--) {
Node child = previous.getChildren().get(i);
children.add(0, child);
child.setParent(this);
}
previous.setChildren(null);
previous.setEntries(null);
previous.setParent(null);
parent.getChildren().remove(previous);
validate(this, tree);
parent.updateRemove(tree);
// 同后面节点合并
} else if (next != null
&& (next.getChildren().size() <= tree.getOrder() / 2 || next.getChildren().size() <= 2)) {
for (int i = 0; i < next.getChildren().size(); i++) {
Node child = next.getChildren().get(i);
children.add(child);
child.setParent(this);
}
next.setChildren(null);
next.setEntries(null);
next.setParent(null);
parent.getChildren().remove(next);
validate(this, tree);
parent.updateRemove(tree);
}
}
}
}
}
public void remove(Comparable key, BplusTree tree){
//如果是叶子节点
if (isLeaf){
//如果不包含该关键字，则直接返回
if (!contains(key)){
return;
}
//如果既是叶子节点又是跟节点，直接删除
if (isRoot) {
remove(key);
}else {
//如果关键字数大于M / 2，直接删除
if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) {
remove(key);
}else {
//如果自身关键字数小于M / 2，并且前节点关键字数大于M / 2，则从其处借补
if (previous != null
&& previous.getEntries().size() > tree.getOrder() / 2
&& previous.getEntries().size() > 2
&& previous.getParent() == parent) {
int size = previous.getEntries().size();
Entry<Comparable, Object> entry = previous.getEntries().get(size - 1);
previous.getEntries().remove(entry);
//添加到首位
entries.add(0, entry);
remove(key);
//如果自身关键字数小于M / 2，并且后节点关键字数大于M / 2，则从其处借补
}else if (next != null
&& next.getEntries().size() > tree.getOrder() / 2
&& next.getEntries().size() > 2
&& next.getParent() == parent) {
Entry<Comparable, Object> entry = next.getEntries().get(0);
next.getEntries().remove(entry);
//添加到末尾
entries.add(entry);
remove(key);
//否则需要合并叶子节点
}else {
//同前面节点合并
if (previous != null
&& (previous.getEntries().size() <= tree.getOrder() / 2 || previous.getEntries().size() <= 2)
&& previous.getParent() == parent) {
for (int i = previous.getEntries().size() - 1; i >=0; i--) {
//从末尾开始添加到首位
entries.add(0, previous.getEntries().get(i));
}
remove(key);
previous.setParent(null);
previous.setEntries(null);
parent.getChildren().remove(previous);
//更新链表
if (previous.getPrevious() != null) {
Node temp = previous;
temp.getPrevious().setNext(this);
previous = temp.getPrevious();
temp.setPrevious(null);
temp.setNext(null);
}else {
tree.setHead(this);
previous.setNext(null);
previous = null;
}
//同后面节点合并
}else if(next != null
&& (next.getEntries().size() <= tree.getOrder() / 2 || next.getEntries().size() <= 2)
&& next.getParent() == parent){
for (int i = 0; i < next.getEntries().size(); i++) {
//从首位开始添加到末尾
entries.add(next.getEntries().get(i));
}
remove(key);
next.setParent(null);
next.setEntries(null);
parent.getChildren().remove(next);
//更新链表
if (next.getNext() != null) {
Node temp = next;
temp.getNext().setPrevious(this);
next = temp.getNext();
temp.setPrevious(null);
temp.setNext(null);
}else {
next.setPrevious(null);
next = null;
}
}
}
}
parent.updateRemove(tree);
}
//如果不是叶子节点
}else {
//如果key小于等于节点最左边的key，沿第一个子节点继续搜索
if (key.compareTo(entries.get(0).getKey()) <= 0) {
children.get(0).remove(key, tree);
//如果key大于节点最右边的key，沿最后一个子节点继续搜索
}else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) {
children.get(children.size()-1).remove(key, tree);
//否则沿比key大的前一个子节点继续搜索
}else {
for (int i = 0; i < entries.size(); i++) {
if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) {
children.get(i).remove(key, tree);
break;
}
}
}
}
}
/** 判断当前节点是否包含该关键字*/
protected boolean contains(Comparable key) {
for (Entry<Comparable, Object> entry : entries) {
if (entry.getKey().compareTo(key) == 0) {
return true;
}
}
return false;
}
/** 插入到当前节点的关键字中*/
protected void insertOrUpdate(Comparable key, Object obj){
Entry<Comparable, Object> entry = new SimpleEntry<Comparable, Object>(key, obj);
//如果关键字列表长度为0，则直接插入
if (entries.size() == 0) {
entries.add(entry);
return;
}
//否则遍历列表
for (int i = 0; i < entries.size(); i++) {
//如果该关键字键值已存在，则更新
if (entries.get(i).getKey().compareTo(key) == 0) {
entries.get(i).setValue(obj);
return;
//否则插入
}else if (entries.get(i).getKey().compareTo(key) > 0){
//插入到链首
if (i == 0) {
entries.add(0, entry);
return;
//插入到中间
}else {
entries.add(i, entry);
return;
}
}
}
//插入到末尾
entries.add(entries.size(), entry);
}
/** 删除节点*/
protected void remove(Comparable key){
int index = -1;
for (int i = 0; i < entries.size(); i++) {
if (entries.get(i).getKey().compareTo(key) == 0) {
index = i;
break;
}
}
if (index != -1) {
entries.remove(index);
}
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public boolean isLeaf() {
return isLeaf;
}
public void setLeaf(boolean isLeaf) {
this.isLeaf = isLeaf;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public List<Entry<Comparable, Object>> getEntries() {
return entries;
}
public void setEntries(List<Entry<Comparable, Object>> entries) {
this.entries = entries;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
public boolean isRoot() {
return isRoot;
}
public void setRoot(boolean isRoot) {
this.isRoot = isRoot;
}
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("isRoot: ");
sb.append(isRoot);
sb.append(", ");
sb.append("isLeaf: ");
sb.append(isLeaf);
sb.append(", ");
sb.append("keys: ");
for (Entry entry : entries){
sb.append(entry.getKey());
sb.append(", ");
}
sb.append(", ");
return sb.toString();
}
}
分享到：
发表评论
相关推荐
### Kaldi决策树状态绑定学习笔记一：理解与实践 #### 概述 本文档将深入探讨Kaldi中决策树状态绑定的相关知识点，包括决策树的原理、关键数据结构、统计量累积方法以及其实现过程中的注意事项。通过本文档的学习...
B0017机器学习学习笔记.pdf和B0008MLN_机器学习学习笔记.pdf可能包括了基本的机器学习模型，如线性回归、逻辑回归、支持向量机（SVM）、决策树以及随机森林等。此外，笔记可能还会讨论无监督学习中的聚类算法，如K-...
Oracle 12c 学习笔记 本文档旨在为读者提供 Oracle 12c 的基础知识，涵盖 Oracle 的基本介绍、存储的介绍、基本数据对象、表空间的管理、升级到 Oracle 12c 以及数据库的物理布局和存储管理等方面。 Oracle 体系...
6. **特殊类型的树**：除了基本的树，还有许多特殊类型的树，如堆（优先队列的实现）、B树和B+树（用于数据库索引）、Trie树（用于字符串查找）等，它们各自有独特的结构和用途。 在《数据结构学习笔记-第八篇》中...
4. **索引与查询优化**：Oracle提供了多种类型的索引，如B树、位图、函数索引等，以及查询优化器，学习笔记会阐述如何创建和使用索引来提高查询性能。 5. **安全性**：Oracle有强大的用户权限管理和角色机制，笔记...
jquery 教程笔记 jquery 是一个功能强大且灵活的 JavaScript 库，它提供了很多实用的方法来帮助开发者快速构建 web 应用程序。下面是 jquery 的一些重要知识点： 选择器 jquery 中的选择器是非常强大的，它可以...
树结构 draw.io图 二叉树、顺序树、树的链式存储结构、树的数组存储结构、欧拉树 绘图软件为免费开源软件draw.io
通过阅读《数据结构高分笔记》精彩摘录之考研数据结构必备基础知识.pdf和《数据结构高分笔记》精彩摘录之B-树.pdf，读者可以深入理解这些概念，并获得实际应用的指导。学习数据结构不仅是为了解决编程问题，更是为了...
B树和B+树是常见的索引结构，而哈希索引则适用于等值查询。 事务是数据库操作的基本单元，具有ACID特性：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。这些保证了...
【尚硅谷周阳Mysql高级思维导图脑图学习笔记】是针对MySQL数据库系统的一份高级学习资料，包含了丰富的知识体系，旨在帮助学习者深入理解并掌握MySQL的高级特性和优化技巧。这份资源以.mmap格式提供，这是一种专业的...
5. **索引与优化**：B树、哈希索引的工作原理，如何创建和管理索引，以及使用EXPLAIN分析查询性能。 6. **存储引擎**：InnoDB和MyISAM的对比，事务处理、行级锁定、外键支持等特性，以及其它存储引擎如Memory、...
- 索引原理: 通过构建特殊的数据结构，如B树，加速数据检索。 - **分表**: 减少单个表的数据量(sharding)。 - 分表策略: 按时间、按ID范围等方式分散数据到多个表中。 #### 五、数据库部署与管理 - **服务器集群*...
红黑树是一种自平衡二叉查找树，确保了树的高度平衡，从而提高查找效率。 关联容器的迭代器允许按照键值的大小顺序遍历容器，迭代器`begin()`指向最小键的元素，`end()`指向最大键元素之后的位置。常见的操作包括：...
MFC 编程学习笔记 MFC（Microsoft Foundation Classes）是一种基于Windows操作系统的应用程序框架，提供了一组强大的类库和工具，帮助开发者快速创建Windows应用程序。本笔记总结了MFC 编程的一些基本概念和控件...
索引分为B树索引、哈希索引和全文索引，理解它们的工作原理和适用场景是优化查询的关键。 事务处理是确保数据一致性的核心机制，包括ACID（原子性、一致性、隔离性和持久性）四大特性。你将学习到如何使用BEGIN、...
3. 树结构：二叉树、平衡树（AVL树、红黑树）、B树、B+树等，它们在数据库索引、文件系统等方面有广泛应用。 4. 图算法：Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法、Prim最小生成树算法、Kruskal...
Oracle11g支持多种类型的索引，包括B树索引、位图索引和函数索引。理解何时使用哪种类型的索引，以及如何创建和优化索引，对于数据库性能至关重要。 数据库安全性是另一个关键话题。Oracle11g提供了用户管理和权限...
此外，索引的创建和优化对查询性能有着显著影响，应合理设计主键和唯一索引，以及考虑使用B树、哈希索引等不同类型的索引。 数据库设计时需遵循范式理论，如第一范式（1NF）、第二范式（2NF）、第三范式（3NF），以...