Requisito previo: Introducción de árboles B+
En este artículo, discutiremos cómo insertar un Node en B+ Tree . Durante la inserción, se deben seguir las siguientes propiedades de B+ Tree :
- Cada Node, excepto el raíz, puede tener un máximo de M hijos y al menos ceil(M/2) hijos.
- Cada Node puede contener un máximo de M – 1 claves y un mínimo de ceil(M/2) – 1 claves.
- La raíz tiene al menos dos hijos y al menos una clave de búsqueda.
- Mientras que el desbordamiento de inserción del Node ocurre cuando contiene más de M – 1 valores de clave de búsqueda.
Aquí M es el orden del árbol B+.
Pasos para la inserción en B+ Tree
- Cada elemento se inserta en un Node hoja. Entonces, vaya al Node de hoja apropiado.
- Inserte la llave en el Node hoja en orden creciente solo si no hay desbordamiento. Si hay un desbordamiento, continúe con los siguientes pasos que se mencionan a continuación para tratar el desbordamiento mientras se mantienen las propiedades del árbol B+.
Propiedades para la inserción Árbol B+
Caso 1: desbordamiento en el Node hoja
- Dividir el Node hoja en dos Nodes.
- El primer Node contiene valores ceil((m-1)/2) .
- El segundo Node contiene los valores restantes.
- Copie el valor de clave de búsqueda más pequeño del segundo Node al Node principal. (Sesgo a la derecha)
A continuación se muestra la ilustración de la inserción de 8 en el árbol B+ de orden de 5:
Caso 2: Desbordamiento en Node no hoja
- Dividir el Node no hoja en dos Nodes.
- El primer Node contiene valores ceil(m/2)-1.
- Mueva el más pequeño entre los restantes al padre.
- El segundo Node contiene las claves restantes.
A continuación se muestra la ilustración de la inserción de 15 en el árbol B+ de orden de 5:
Ejemplo para ilustrar la inserción en un árbol B+
Problema: inserte los siguientes valores clave 6, 16, 26, 36, 46 en un árbol B+ con orden = 3.
Solución:
Paso 1: el orden es 3, por lo que como máximo en un Node solo puede haber 2 valores clave de búsqueda. Como la inserción ocurre en un Node de hoja solo en un árbol B+, inserte el valor de la clave de búsqueda 6 y 16 en orden creciente en el Node. A continuación se muestra la ilustración del mismo:
Paso 2: no podemos insertar 26 en el mismo Node porque causa un desbordamiento en el Node hoja. Tenemos que dividir el Node hoja de acuerdo con las reglas. La primera parte contiene valores ceil((3-1)/2) , es decir, solo 6 . El segundo Node contiene los valores restantes, es decir, 16 y 26 . Luego copie también el valor de clave de búsqueda más pequeño del segundo Node al Node principal, es decir, 16 al Node principal. A continuación se muestra la ilustración del mismo:
Paso 3: ahora el siguiente valor es 36 que se insertará después de 26 pero en ese Node, causa un desbordamiento nuevamente en ese Node hoja. De nuevo, siga los pasos anteriores para dividir el Node. La primera parte contiene valores ceil((3-1)/2) , es decir, solo 16 . El segundo Node contiene los valores restantes, es decir, 26 y 36 . Luego copie también el valor de clave de búsqueda más pequeño del segundo Node al Node principal, es decir, 26 al Node principal. A continuación se muestra la ilustración del mismo:
La ilustración se muestra en el siguiente diagrama.
Paso 4: ahora tenemos que insertar 46 que se insertará después de 36 pero provoca un desbordamiento en el Node hoja. Entonces dividimos el Node de acuerdo con las reglas. La primera parte contiene 26 y la segunda parte contiene 36 y 46 , pero ahora también tenemos que copiar 36 en el Node principal, pero provoca un desbordamiento ya que solo se pueden acomodar dos valores de clave de búsqueda en un Node. Ahora siga los pasos para lidiar con el desbordamiento en el Node que no es hoja.
El primer Node contiene valores ceil(3/2)-1, es decir, ’16’.
Mueva el más pequeño entre los restantes al padre, es decir, ’26’ será el nuevo Node padre.
El segundo Node contiene las claves restantes, es decir, ’36’ y el resto de los Nodes hoja siguen siendo los mismos. A continuación se muestra la ilustración del mismo:
A continuación se muestra la implementación de la inserción en el árbol B+:
C++
// C++ program for implementing B+ Tree
#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int MAX = 3;
// BP node
class Node {
bool IS_LEAF;
int *key, size;
Node** ptr;
friend class BPTree;
public:
Node();
};
// BP tree
class BPTree {
Node* root;
void insertInternal(int,
Node*,
Node*);
Node* findParent(Node*, Node*);
public:
BPTree();
void search(int);
void insert(int);
void display(Node*);
Node* getRoot();
};
// Constructor of Node
Node::Node()
{
key = new int[MAX];
ptr = new Node*[MAX + 1];
}
// Initialise the BPTree Node
BPTree::BPTree()
{
root = NULL;
}
// Function to find any element
// in B+ Tree
void BPTree::search(int x)
{
// If tree is empty
if (root == NULL) {
cout << "Tree is empty\n";
}
// Traverse to find the value
else {
Node* cursor = root;
// Till we reach leaf node
while (cursor->IS_LEAF == false) {
for (int i = 0;
i < cursor->size; i++) {
// If the element to be
// found is not present
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
// If reaches end of the
// cursor node
if (i == cursor->size - 1) {
cursor = cursor->ptr[i + 1];
break;
}
}
}
// Traverse the cursor and find
// the node with value x
for (int i = 0;
i < cursor->size; i++) {
// If found then return
if (cursor->key[i] == x) {
cout << "Found\n";
return;
}
}
// Else element is not present
cout << "Not found\n";
}
}
// Function to implement the Insert
// Operation in B+ Tree
void BPTree::insert(int x)
{
// If root is null then return
// newly created node
if (root == NULL) {
root = new Node;
root->key[0] = x;
root->IS_LEAF = true;
root->size = 1;
}
// Traverse the B+ Tree
else {
Node* cursor = root;
Node* parent;
// Till cursor reaches the
// leaf node
while (cursor->IS_LEAF
== false) {
parent = cursor;
for (int i = 0;
i < cursor->size;
i++) {
// If found the position
// where we have to insert
// node
if (x < cursor->key[i]) {
cursor
= cursor->ptr[i];
break;
}
// If reaches the end
if (i == cursor->size - 1) {
cursor
= cursor->ptr[i + 1];
break;
}
}
}
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i]
&& i < cursor->size) {
i++;
}
for (int j = cursor->size;
j > i; j--) {
cursor->key[j]
= cursor->key[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[cursor->size]
= cursor->ptr[cursor->size - 1];
cursor->ptr[cursor->size - 1] = NULL;
}
else {
// Create a newLeaf node
Node* newLeaf = new Node;
int virtualNode[MAX + 1];
// Update cursor to virtual
// node created
for (int i = 0; i < MAX; i++) {
virtualNode[i]
= cursor->key[i];
}
int i = 0, j;
// Traverse to find where the new
// node is to be inserted
while (x > virtualNode[i]
&& i < MAX) {
i++;
}
// Update the current virtual
// Node to its previous
for (int j = MAX + 1;
j > i; j--) {
virtualNode[j]
= virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf->IS_LEAF = true;
cursor->size = (MAX + 1) / 2;
newLeaf->size
= MAX + 1 - (MAX + 1) / 2;
cursor->ptr[cursor->size]
= newLeaf;
newLeaf->ptr[newLeaf->size]
= cursor->ptr[MAX];
cursor->ptr[MAX] = NULL;
// Update the current virtual
// Node's key to its previous
for (i = 0;
i < cursor->size; i++) {
cursor->key[i]
= virtualNode[i];
}
// Update the newLeaf key to
// virtual Node
for (i = 0, j = cursor->size;
i < newLeaf->size;
i++, j++) {
newLeaf->key[i]
= virtualNode[j];
}
// If cursor is the root node
if (cursor == root) {
// Create a new Node
Node* newRoot = new Node;
// Update rest field of
// B+ Tree Node
newRoot->key[0] = newLeaf->key[0];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newLeaf;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
}
else {
// Recursive Call for
// insert in internal
insertInternal(newLeaf->key[0],
parent,
newLeaf);
}
}
}
}
// Function to implement the Insert
// Internal Operation in B+ Tree
void BPTree::insertInternal(int x,
Node* cursor,
Node* child)
{
// If we doesn't have overflow
if (cursor->size < MAX) {
int i = 0;
// Traverse the child node
// for current cursor node
while (x > cursor->key[i]
&& i < cursor->size) {
i++;
}
// Traverse the cursor node
// and update the current key
// to its previous node key
for (int j = cursor->size;
j > i; j--) {
cursor->key[j]
= cursor->key[j - 1];
}
// Traverse the cursor node
// and update the current ptr
// to its previous node ptr
for (int j = cursor->size + 1;
j > i + 1; j--) {
cursor->ptr[j]
= cursor->ptr[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[i + 1] = child;
}
// For overflow, break the node
else {
// For new Interval
Node* newInternal = new Node;
int virtualKey[MAX + 1];
Node* virtualPtr[MAX + 2];
// Insert the current list key
// of cursor node to virtualKey
for (int i = 0; i < MAX; i++) {
virtualKey[i] = cursor->key[i];
}
// Insert the current list ptr
// of cursor node to virtualPtr
for (int i = 0; i < MAX + 1; i++) {
virtualPtr[i] = cursor->ptr[i];
}
int i = 0, j;
// Traverse to find where the new
// node is to be inserted
while (x > virtualKey[i]
&& i < MAX) {
i++;
}
// Traverse the virtualKey node
// and update the current key
// to its previous node key
for (int j = MAX + 1;
j > i; j--) {
virtualKey[j]
= virtualKey[j - 1];
}
virtualKey[i] = x;
// Traverse the virtualKey node
// and update the current ptr
// to its previous node ptr
for (int j = MAX + 2;
j > i + 1; j--) {
virtualPtr[j]
= virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal->IS_LEAF = false;
cursor->size
= (MAX + 1) / 2;
newInternal->size
= MAX - (MAX + 1) / 2;
// Insert new node as an
// internal node
for (i = 0, j = cursor->size + 1;
i < newInternal->size;
i++, j++) {
newInternal->key[i]
= virtualKey[j];
}
for (i = 0, j = cursor->size + 1;
i < newInternal->size + 1;
i++, j++) {
newInternal->ptr[i]
= virtualPtr[j];
}
// If cursor is the root node
if (cursor == root) {
// Create a new root node
Node* newRoot = new Node;
// Update key value
newRoot->key[0]
= cursor->key[cursor->size];
// Update rest field of
// B+ Tree Node
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newInternal;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
}
else {
// Recursive Call to insert
// the data
insertInternal(cursor->key[cursor->size],
findParent(root,
cursor),
newInternal);
}
}
}
// Function to find the parent node
Node* BPTree::findParent(Node* cursor,
Node* child)
{
Node* parent;
// If cursor reaches the end of Tree
if (cursor->IS_LEAF
|| (cursor->ptr[0])->IS_LEAF) {
return NULL;
}
// Traverse the current node with
// all its child
for (int i = 0;
i < cursor->size + 1; i++) {
// Update the parent for the
// child Node
if (cursor->ptr[i] == child) {
parent = cursor;
return parent;
}
// Else recursively traverse to
// find child node
else {
parent
= findParent(cursor->ptr[i],
child);
// If parent is found, then
// return that parent node
if (parent != NULL)
return parent;
}
}
// Return parent node
return parent;
}
// Function to get the root Node
Node* BPTree::getRoot()
{
return root;
}
// Driver Code
int main()
{
BPTree node;
// Create B+ Tree
node.insert(6);
node.insert(16);
node.insert(26);
node.insert(36);
node.insert(46);
// Function Call to search node
// with value 16
node.search(16);
return 0;
}
Python3
# Python3 program for implementing B+ Tree
MAX = 3
# BP node
class Node :
def __init__(self):
self.IS_LEAF=False
self.key, self.size=[None]*MAX,0
self.ptr=[None]*(MAX+1)
# BP tree
class BPTree :
# Initialise the BPTree Node
def __init__(self):
self.root = None
# Function to find any element
# in B+ Tree
def search(self,x):
# If tree is empty
if (self.root == None) :
cout << "Tree is empty\n"
# Traverse to find the value
else :
cursor = self.root
# Till we reach leaf node
while (not cursor.IS_LEAF) :
for i in range(cursor.size) :
# If the element to be
# found is not present
if (x < cursor.key[i]) :
cursor = cursor.ptr[i]
break
# If reaches end of the
# cursor node
if (i == cursor.size - 1) :
cursor = cursor.ptr[i + 1]
break
# Traverse the cursor and find
# the node with value x
for i in range(cursor.size):
# If found then return
if (cursor.key[i] == x) :
print("Found")
return
# Else element is not present
print("Not found")
# Function to implement the Insert
# Operation in B+ Tree
def insert(self, x):
# If root is None then return
# newly created node
if (self.root == None) :
self.root = Node()
self.root.key[0] = x
self.root.IS_LEAF = True
self.root.size = 1
# Traverse the B+ Tree
else :
cursor = self.root
parent=None
# Till cursor reaches the
# leaf node
while (not cursor.IS_LEAF) :
parent = cursor
for i in range(cursor.size) :
# If found the position
# where we have to insert
# node
if (x < cursor.key[i]) :
cursor = cursor.ptr[i]
break
# If reaches the end
if (i == cursor.size - 1) :
cursor = cursor.ptr[i + 1]
break
if (cursor.size < MAX) :
i = 0
while (i < cursor.size and x > cursor.key[i]):
i+=1
for j in range(cursor.size,i,-1):
cursor.key[j] = cursor.key[j - 1]
cursor.key[i] = x
cursor.size+=1
cursor.ptr[cursor.size] = cursor.ptr[cursor.size - 1]
cursor.ptr[cursor.size - 1] = None
else :
# Create a newLeaf node
newLeaf = Node()
virtualNode=[None]*(MAX + 1)
# Update cursor to virtual
# node created
for i in range(MAX):
virtualNode[i] = cursor.key[i]
i = 0
# Traverse to find where the new
# node is to be inserted
while (i < MAX and x > virtualNode[i]) :
i+=1
# Update the current virtual
# Node to its previous
for j in range(MAX,i,-1) :
virtualNode[j] = virtualNode[j - 1]
virtualNode[i] = x
newLeaf.IS_LEAF = True
cursor.size = int((MAX + 1) / 2)
newLeaf.size = int(MAX + 1 - (MAX + 1) / 2)
cursor.ptr[cursor.size] = newLeaf
newLeaf.ptr[newLeaf.size] = cursor.ptr[MAX]
cursor.ptr[MAX] = None
# Update the current virtual
# Node's key to its previous
for i in range(cursor.size):
cursor.key[i] = virtualNode[i]
# Update the newLeaf key to
# virtual Node
j=cursor.size
for i in range(newLeaf.size):
newLeaf.key[i] = virtualNode[j]
j+=1
# If cursor is the root node
if (cursor == self.root) :
# Create a new Node
newRoot = Node()
# Update rest field of
# B+ Tree Node
newRoot.key[0] = newLeaf.key[0]
newRoot.ptr[0] = cursor
newRoot.ptr[1] = newLeaf
newRoot.IS_LEAF = False
newRoot.size = 1
root = newRoot
else :
# Recursive Call for
# insert in internal
insertInternal(newLeaf.key[0],
parent,
newLeaf)
# Function to implement the Insert
# Internal Operation in B+ Tree
def insertInternal(x, cursor, child):
# If we doesn't have overflow
if (cursor.size < MAX) :
i = 0
# Traverse the child node
# for current cursor node
while (x > cursor.key[i] and i < cursor.size) :
i+=1
# Traverse the cursor node
# and update the current key
# to its previous node key
for j in range(cursor.size,i,-1) :
cursor.key[j] = cursor.key[j - 1]
# Traverse the cursor node
# and update the current ptr
# to its previous node ptr
for j in range(cursor.size + 1, i + 1,-1):
cursor.ptr[j] = cursor.ptr[j - 1]
cursor.key[i] = x
cursor.size+=1
cursor.ptr[i + 1] = child
# For overflow, break the node
else :
# For new Interval
newInternal = Node()
virtualKey=[None]*(MAX + 1)
virtualPtr=[None]*(MAX + 2)
# Insert the current list key
# of cursor node to virtualKey
for i in range(MAX) :
virtualKey[i] = cursor.key[i]
# Insert the current list ptr
# of cursor node to virtualPtr
for i in range(MAX + 1):
virtualPtr[i] = cursor.ptr[i]
i = 0
# Traverse to find where the new
# node is to be inserted
while (x > virtualKey[i] and i < MAX) :
i+=1
# Traverse the virtualKey node
# and update the current key
# to its previous node key
for j in range(MAX + 1,i,-1):
virtualKey[j] = virtualKey[j - 1]
virtualKey[i] = x
# Traverse the virtualKey node
# and update the current ptr
# to its previous node ptr
for j in range(MAX + 2, i + 1,-1) :
virtualPtr[j] = virtualPtr[j - 1]
virtualPtr[i + 1] = child
newInternal.IS_LEAF = false
cursor.size = (MAX + 1) / 2
newInternal.size = MAX - (MAX + 1) / 2
# Insert new node as an
# internal node
j = cursor.size + 1
for i in range(newInternal.size):
newInternal.key[i] = virtualKey[j]
j+=1
j = cursor.size + 1
for i in range(newInternal.size):
newInternal.ptr[i] = virtualKey[j]
j+=1
# If cursor is the root node
if (cursor == self.root) :
# Create a new root node
newRoot = self.root
# Update key value
newRoot.key[0] = cursor.key[cursor.size]
# Update rest field of
# B+ Tree Node
newRoot.ptr[0] = cursor
newRoot.ptr[1] = newInternal
newRoot.IS_LEAF = false
newRoot.size = 1
root = newRoot
else :
# Recursive Call to insert
# the data
insertInternal(cursor.key[cursor.size],
findParent(root,
cursor),
newInternal)
# Function to find the parent node
def findParent(self, cursor, child):
# If cursor reaches the end of Tree
if (cursor.IS_LEAF or (cursor.ptr[0]).IS_LEAF) :
return None
# Traverse the current node with
# all its child
for i in range(cursor.size + 1) :
# Update the parent for the
# child Node
if (cursor.ptr[i] == child) :
parent = cursor
return parent
# Else recursively traverse to
# find child node
else :
parent = findParent(cursor.ptr[i], child)
# If parent is found, then
# return that parent node
if (parent != None):
return parent
# Return parent node
return parent
# Function to get the root Node
def getRoot(self):
return self.root
# Driver Code
if __name__=='__main__':
node=BPTree()
# Create B+ Tree
node.insert(6)
node.insert(16)
node.insert(26)
node.insert(36)
node.insert(46)
# Function Call to search node
# with value 16
node.search(16)
Producción:
Found
Complejidad de tiempo: O (logn)
Espacio auxiliar: O (logn)
Publicación traducida automáticamente
Artículo escrito por simran_rawat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA