Árbol Patricia de aprendizaje rápido

Etiquetas: aprendizaje rápido

Patricia Tree

Si la "base" de un árbol de base es 2 o una potencia entera de 2, se denomina "árbol de Patricia" y, a veces, se lo considera directamente como un árbol de base.

• En Ethereum, el carácter Hex se usa como el conjunto de caracteres clave, que es el árbol de Patricia con base 16

• En la estructura de árbol de Ethereum, cada nodo puede tener hasta 16 nodos secundarios, más valor, por lo que hay un total de 17 posiciones de "ranuras".

• El árbol de Patricia en Ethereum agrega algunas estructuras de datos adicionales, principalmente para resolver problemas de eficiencia

MPT（Merkel Patricia Tree）

• El árbol Merkel-Patricia es una combinación del árbol Merkel y el árbol Patricia

• La implementación en Ethereum usa codificación Hex para la clave, y cada carácter Hex es un nibble (medio byte)

• Al atravesar la ruta, solo se accede a un nibble de un nodo. La mayoría de los nodos son una matriz que contiene 17 elementos; 16 de ellos usan caracteres hexadecimales como valor de índice para almacenar el puntero del siguiente nibble en la ruta; el otro almacena la ruta if En este punto, el recorrido ha terminado y es necesario devolver el valor final. Estos nodos se denominan "nodos de rama".

• Cada elemento del nodo de sucursal almacena un puntero al nodo del siguiente nivel. A diferencia del método tradicional, MPT usa el hash del nodo puntiagudo para representar este puntero; cada nodo usa el hash del siguiente nodo como parte de su contenido de almacenamiento, realizando así la estructura de árbol de Merkel y asegurando la validez de la verificación de datos Sexo

Clasificación del nodo MPT

Los nodos en MPT tienen las siguientes categorías:

• Nodo nulo (NULL)

• Representa una cadena vacía

• Rama

• Un nodo de 17 elementos, la estructura es [v0… v15, vt]

• Nodo de hoja (hoja)

• Tiene dos elementos, encodedPath y value value

• Extensión

• Tiene dos elementos, encodedPath y key

Optimización de la estructura de datos en MPT

• Para una longitud de ruta de 64 caracteres, es muy probable que encuentre en un cierto nodo que al menos una ruta a continuación no tiene una bifurcación; esto es difícil de evitar

• Por supuesto, todavía podemos usar el nodo de rama estándar para representar, es obligatorio que este nodo debe tener 16 índices completos, y a las 15 posiciones que no se usan se les asignan valores vacíos; pero esto es un poco estúpido

• Al configurar el "nodo de expansión", puede acortar eficazmente la ruta de acceso, comprimir la larga relación jerárquica en un par clave-valor y evitar el desperdicio de espacio innecesario.

• La forma de contenido del nodo de extensión es [encodedPath, clave], donde encodedPath contiene la parte de la ruta que no se bifurca a continuación y la clave es un puntero al siguiente nodo (hash, es decir, la ubicación de almacenamiento en la base de datos subyacente)

• Nodo hoja: si no hay una ruta de bifurcación después de un determinado nodo, entonces este es un nodo hoja y su segundo elemento es su valor

Ruta de "perro" después de la compresión