Estoy bastante familiarizado con un árbol B, principalmente teniendo que mantener las bases de datos bien alimentadas con electricidad, aire acondicionado y espacio en el disco duro. Me asocio con una lista doble (¿duplicado [es decir, ey]?).
Hoy, uno de los desarrolladores en el almuerzo mencionó un árbol R.
Me subí a Wikipedia y comencé a leer. Parecía horrible como un árbol B más alto. Desafortunadamente, no tener un fondo matemático profundo hace que sea difícil entender de qué están hablando algunos de mis compañeros de trabajo.
Esperaba que alguien pudiera aclarar algunas diferencias entre un árbol B y un árbol R. Probablemente termine preguntando a los chicos de todos modos, pero no hay garantía de que respondan mi pregunta. Es más que probable que empiecen a divagar acerca de que Dios sabe qué. . .
fuente
Respuestas:
Un árbol R puede considerarse como la generalización de un árbol b. Cuando un árbol b proporciona acceso O (log n) sobre un "rango acotado" de las claves que contiene, un árbol R proporciona acceso O (log n) sobre una "región dimensional K" de las claves que contiene.
Si quisiera asignar códigos postales a los nombres de los condados, podría usar un B-Tree, ya que podría preguntar "¿Cuáles son todos los condados con códigos postales entre 60000 y 61000?" Sin embargo, un B-Tree no sería adecuado para asignar coordenadas GPS a los nombres de los condados para consultas como "¿Cuáles son todos los condados dentro de las 100 millas de Chicago?", Ya que solo ordena sus llaves en una sola dimensión. Un R-Tree divide sus claves de acuerdo con los cuadros delimitadores superpuestos, por lo que es una forma natural de almacenar claves cuando necesita consultar en múltiples dimensiones.
fuente
La mayoría de las estructuras de árbol pueden reducirse a alguna forma de lista vinculada, siempre que ignore cómo se construye la lista (específicamente, cómo se agregan y eliminan elementos, y cómo se reequilibran los nodos, si corresponde). Es esencialmente el algoritmo de inserción / eliminación / recuperación que distingue una estructura de datos de otra.
Los nodos en un R-Tree generalmente contienen un cuadro delimitador, que le permite indexar ubicaciones de manera eficiente, como podría necesitar si desea buscar registros "cerca" de una ubicación en particular. Los elementos en un B-Tree tienen un orden más simple; puede comparar directamente si algo es mayor o igual que otro elemento. En un R-Tree, el propósito de cada entrada es determinar qué elementos están contenidos en un cuadro delimitador.
Un B-Tree le permite buscar eficientemente los elementos que se pueden pedir en la memoria secundaria (como un disco duro), y un R-Tree le permite buscar eficientemente elementos que están "en" o "cerca" de un punto particular o cuadro delimitador, también en memoria secundaria.
fuente