1sds
estructura de datos sds
¿Cuáles son las ventajas de los sds en comparación con las cuerdas c
1 La longitud de la cadena se puede obtener directamente en el momento de la carga de o(1), y c necesita ser atravesada, que es O(n)
2 La cadena se puede modificar sin causar desbordamiento de memoria o fuga de memoria. Cuando se modifican los sds, se alargará automáticamente si la longitud no es suficiente y, a continuación, modificará la cadena, actualizará los campos free y len, si la cadena c no se expande Si la longitud de la cadena modificada es mayor que la longitud de la cadena antes de la modificación, puede provocar el desbordamiento de memoria. Además, si utiliza la función trim() en la cadena c para eliminar espacios, la cadena c no reducirá automáticamente el uso de memoria. Causará desbordamiento de memoria
3sds es binario seguro, c cadena termina con ‘ ’ de forma predeterminada, por lo que puede que no esté disponible al almacenar contenido multimedia como audio y vídeo, mientras que sds no tendrá este problema
4sds agregará ’ al final, para que los sds puedan usar algunas API de lenguaje C
El principio de la asignación de memoria sds
Cuando se expanden los sds, cuando el tamaño de los sds es inferior a 1 m, la capacidad se duplicará cada vez. Cuando sds es mayor que 1m, añadir 1m cada vez, y el máximo es 512m.
2 listas vinculadas,
3 diccionarios
Diccionario para guardar datos y resolver conflictos
1 Calcule el valor hash
2 Guarde los datos en la ubicación hash correspondiente y continúe agregando datos a la siguiente cadena
Cálculo del factor de carga
Cálculo de la capacidad después de la expansión
Es decir, por ejemplo, la capacidad actual es 5., tamaño = 4, luego después de la expansión es 16, porque 5 * 2 = 10, el más cercano 2^n es 16.
Cómo expandirse
Con el hash progresivo, se creará un diccionario expandido para coexistir con puntos atómicos, luego los datos se moverán lentamente y, finalmente, se eliminará el diccionario de datos original.
4 tabla de saltos
La tabla jump es agregar un índice de varios niveles a la estructura de datos original para facilitar la búsqueda de datos
5 conjunto entero
Beneficios de conjuntos enteros
1redis guarda enteros con 16 bits, 32 bits y 64 bits. Redis utiliza un método de actualización progresiva al guardar conjuntos enteros. El mayor número de dígitos se utiliza como el número de dígitos de los datos guardados. Si todos son 16, luego usando almacenamiento de 16 bits, cómo mezclar. Por ejemplo, 14632 anterior requiere 32 bits, luego el todo se actualizará a 32 bits. Si se elimina 14632, se degradará a 16 bits en su conjunto. La ventaja de esto es que puede guardar memoria.
6 tabla de compresión zipList
previous_entity_length: Registre la longitud del nodo anterior. Si el tamaño del nodo anterior es inferior a 254 bytes, previous_entity_length solo necesita un byte, de lo contrario 5 bytes
codificación: codificación
Problema de actualización de la cadena
Si se inserta un nodo con una longitud de 254 o más en la parte frontal, la previous_entity_length del siguiente nodo aumentará de 1 a 5, lo que hará que el nodo actual también cambie. Si la longitud de los siguientes nodos está entre 251 y 253, entonces se producirá una reacción en cadena, causando que se amplíen todas las longitudes previous_entity_length, lo que conduce a problemas de rendimiento, pero la probabilidad de que se produzcan este tipo de problemas de rendimiento es muy pequeña
7 Principio de la cadena básica de tipo de datos
7 El principio de la lista básica de tipos de datos
Si el tamaño de cada elemento de la lista es inferior a 64 bytes y el número de elementos es inferior a 512, se utiliza la lista comprimida,
De lo contrario, utilice la lista vinculada
8 El principio del tipo de datos básicos hash
Si el tamaño de la clave y el valor de cada par clave-valor es inferior a 64 bytes y el número de elementos es inferior a 512, utilice una lista comprimida
De lo contrario, utilice un diccionario
9 El principio del conjunto de conjunto desordenado de tipo de datos básico
Todos los elementos del conjunto son enteros y el número es inferior a 512,
De lo contrario, utilice hashTable (diccionario)
10El principio del tipo de datos básico ordered set sortSet
Si los elementos del conjunto ordenado son inferiores a 128 y el tamaño de todos los elementos es inferior a 64 bytes, se utiliza la lista ziplist comprimida,
De lo contrario, utilice la lista de omisión + diccionario
Por qué usar diccionario + tabla de saltos
1 Utilizando un diccionario, es conveniente y preciso encontrar los datos correspondientes bajo o (1)
2Adopt una tabla de saltos para facilitar la búsqueda a intervalos,
3 Se pueden añadir dos juntos para lograr una búsqueda rápida
11 Se pueden establecer las condiciones para cuándo utilizar la lista comprimida anterior
.
